Cryptography Basics and Contemporary Practices

Data Security and Cryptology, VII Symmetric Cryptoalgorithms. AES October 14th, 2015 Valdo Praust mois@mois.ee Lecture Course in Estonian IT College Autumn 2015

Two Stages of Cryptography Pre-computer cryptography or traditional cryptography (arvutieelne ehk traditsiooniline kr ptograafia). Uses paper-pencil or some simple mechanical devices (until 1940s). Was a tool only for military, diplomacy and intelligence areas (until 1970-80s). Uses empirical tehcniques (until 1949) Contemporary cryptology or computer- age cryptography, usually called only cryptography ((kaasaja) kr ptograafia). Uses computers as encrypting/breaking tools (since 1940s). Is an essential tool for each e-systems (since 1970-80s). Uses scientific-based algoritms(since 1949)

Contemporary Cryptography an Official Definition (Contemporary) cryptology ((kaasaja) kr ptograafia) is a discipline that embodies the principles, means, and methods for the transformation of data in order to hide their semantic content, prevent their unauthorized use, or prevent their undetected modification (Source: ISO 7498-2)

Basic Concepts of (Contemporary) Cryptology Encryptable (convertable from readable to unreadable form) text is called plaintext (avatekst) Encrypted text (the text which is already converted to unreadable form) is called ciphertext (kr ptogramm) The converting process from plaintext to ciphertext (from readable to unreadable form) is called encryption or encipherment (kr pteerimine, ifreerimine) The converting process from ciphertext back to plaintext (beck to readable form) under normal circumstances is called decryption or deciphering (de ifreerimine)

Basic Concepts of (Contemporary) Cryptology Usually both the enciphering and deciphering processes are performed by using a key or secret key (v ti, salajane v ti) Deciphering is a transforming of a ciphertext into a plaintext using an appropriate key Successful transforming of ciphertext into a plaintext without a key is called breaking a cryptoalgorithm (kr ptoalgoritmi murdmine) In pre-computer (traditional) cryptoalgoritms the key is often undistinguishable from an algoritm itself

Main Properties of Contemporary Cryptology, I Technical descriptions of all wide- spread cryptoalgoritms are usually public. All of security is usually based on a secure key which is used in actual (practical) cases This allows to evaluate the algorthm s security for a wide range of independent experts (without having access to real confidential data which needs a key) In practice the security was usually evaluated by the cryptologists (kr ptoloogid) who are usually deep matematicians by education and specialization

Main Properties of Contemporary Cryptology, II Contemporary cryptology uses always standardized algorithms which are worked out by cryptologists (matematicians). Composing of own algorithms by itself has been already long times history (and remains forever) Composing a secure (practically unbreakable) cryptoalgorithms needs a deep knowledge of cryptology and mathematics As longer the cryptoalgorithm has been in public use (has been available for testing by several experts/cryptologists), it s less probable, that there are effective breaking (cryptoanalytic) methods of it

Main Properties of Contemporary Cryptology, III Contemporary cryptology uses computers. Encrypting with paper and pencil has remained history already for a decades The speed of calculations is very important for both encrypting and cryptanalysis. Computers working performance is some hunderds thousands times faster as human s performance using paper-pencil (GHz s versus 10 Hz) Cryptography (actually the whole cryptology) is one of the many application of informatics

Main Properties of Contemporary Cryptology, IV Contemporary cryptology uses a lot of pre-agreed standards, which are same in all around the world Cryptography is a tool for securing of information systems, but IT tools (software and hardware) are same in all around the world An IT tool with a good (secure), but uncommon cryptoalgorithm is uncompatible with other IT infrastructure components (internet etc)

Main Types of Cryptoalgorithms 1. Symmetric cryptoalgorithms or secret-key crypotoalgorithms are traditional (historical) cryptoalgorithms 2. Asymmetric cryptoalgorithms or public-key crypotoalgorithms are widely spread within last 35 years 3. Cryptographic message digests and similar constructions 4. Special-purpose algorithms for proofing, authentication etc

Secret-Key Cryptoalgorithm Secret-key cryptoalgorithm (salajase v tmega kr ptoalgoritm) or symmetric cryptoalgorithm (s mmeetriline kr ptoalgorithm) is such a cryptoalgorithm where the same secret key is used both for enciphering and deciphering purposes Famous examples: AES (128-, 192- or 256-bit key) IDEA (128-bit key) Skipjack (80-bit key) RC4 (keylength between 40 and bits) (DES (56-bit key)) ?

Secret-Key Cryptoalgorithm

Secret-Key Cryptoalgorithm: Fields of Use transmitting of confidential information using some (interceptable) networks secure storing of confidential information (with an appropriate key management system) secure erasing of confidential data

Public-Key Cryptoalgorithm Public-key cryptoalgorithm (avaliku v tmega kr ptoalgoritm) or asymmetric cryptoalgorithm (as mmeetriline kr ptoalgoritm) uses two keys if we encrypt by one key, we can decrypt it later by another key These keys are mathematically related to each other but there s impossible in practice to found from one key another

Public-Key Cryptoalgorithm: Keys Keys of public-key cryptoalgorithm are called usually public key and private key (avalik v ti ja privaatv ti) Public key is usually known for all parties (is public) Private key is usually known only by a subject or a keypair owner (people, software, server, company, chipcard etc)

Most-of-Spread Public-Key Cryptoalgorithm: RSA The most-of-spread public-key cryptoalgorithm is RSA RSA is considered to be practically secure with no less than 1024-bit keylenght For RSA it is easy to calculate the public key from private key, but it s practically impossible to calculate from public key the private key Public and private key are mathematically related to each other, but finding the private key from public key needs million years or more

Public-Key Cryptoalgorithm: Usage For a key exchanging purposes. We can transmit a symmetric cryptoalgorithm s key in an encrypted manner without any tamper- proof channel. We only need that a public key must be really public For ensuring the integrity. This is the main usage of public-key cryptoalgorithm (and even the main field of contemporary cryptography) Public-key crryptoalgorithm gives a basic idea of a digital signature (digisignatuur, digiallkiri)

Public-Key Cryptoalgorithm: Key Exchange

Public-Key Cryptoalgorithm: an Idea of Digital Signing

Cryptographic Message Digest Cryptographic message digest (kr ptograafiline s numil hend) or cryptographic hash (kr ptor si) is a digest with a fixed small lenght which is calculated from a message by some deterministic mathematical one-way function One-way function ( hesuunaline funktsioon): is such a function which is easily computable but the inverse function (p rdfunktsioon) is practically impossible to perform For a given cryptographic hash it s impossible to find a corresponding message For a given message-hash pair it s impossible to modify a message in a way which remains the hash intact

Cryptographic Message Digest: Usage If we have a given message-hash pair and the hash corresponds to the message then we can always sure that the hash is certainly calculated from the given message Main usage of hashes are ensuring the integrity (usually helps public-key algorithm) Practically secure hash functions find a hash which lenght is at least 160 bit (in enhanced security cases 256 bits)

Cryptographic Message Digest: Principle

Secret-Key Cryptoalgorithm Secret-key cryptoalgorithm (salajase v tmega kr ptoalgoritm) or symmetric cryptoalgorithm (s mmeetriline kr ptoalgorithm) is such a cryptoalgorithm where the same secret key is used both for enciphering and deciphering purposes Is considered to be practically secure if the following two conditons are satisfied: The key is at least 80 bit long (it s considered to be infeasible to perform 280operations in practice), For enhanced security cases 128 bits long There aren t known effective cryptoanalytic methods

Role of Key in Enciphering and Deciphering Process Encrypting or encipherment (kr pteerimine, ifreerimine) needs the using of certain key as a pre-defined queue of bits Opposite process is a decrypting or deciphering (de ifreerimine), which needs a same key in order to restore the initial data (plaintext) from the encrypted text (ciphertext) Without knowing the key the both processes are impossible to peform

Secret-Key Cryptoalgorithm

Secret-Key Cryptoalgorithm Possibility to Break Secret-key cryptoalgorithm is considered to be practically enough secure when the keylength is at least 80 bits (for enhanced security cases 128 bits) DES is already considered insecure because its keylenght is only 56 bits (until 2005 it was allowed to use DES is triple mode as 3DES) Additionally to sufficient keylenght the effective cryptoanalytic attacks must not be known

Most-Of-Spread Algorithms, I 1. AES (keylength 128, 192 or 256 bits). Is international de facto commercial standard since 2001, involves estimatedly 70-80% from all symmetric cryptoalgorithm usages 2. IDEA (keylenght 128 bits). Switzerland, late 1980s 3. CAST5 or CAST-128 (keylenght from 40 to 128 bits). 1996, Carlisle Adams and Stafford Tavares

Most-Of-Spread Algorithms, II 4. Blowfish (variable keylenght up to 448 bits). Bruce Schneier, 1990s 5. RC4. Stream cipher, keylenght between 40 and 256 bits, from 1987 6. DES (keylenght 56 bits). Has been U.S. commercial standard from 1977 and was widely used in all around the world. NB! Today isn t consideres secure because of short keylenght!

Block and Stream Ciphers Symmetric cryptoalgorithm can be divided into block ciphers and stream ciphers. Block ciphers are much more spread than stream ciphers Block cipher (plokk iffer) is an enciphering method where plaintext is divided into the blocks of certain lenght and these blocks are encrypted separately. How and if the encryption result of one block is related from the prevoius blocks, is determined by the block cipher mode, which is currently used Stream cipher (jada iffer) is a method where there is generated a key sequence (v tmejada) from a given secret key. Encryption process is an ordinary XOR operation between plaintext and key sequence

Block Cipher Modes 1. Electronic Codebook Mode, ECM (koodiraamatu re iim) 2. Cipher Block Chaining Mode, CBC (ahelre iim) 3. K-bit Cipher Feedback Mode, CFB ( ifri tagasiside re iim) 4. K-bit Output Feedback Mode, OFB (v ljundi tagasiside re iim)

Electronic Codebook Mode Plaintext blocks are encrypted independently from each other using the same secret key: Disadvatnage: each ciphertext block depends on only one plaintext block repeats in ciphertext

Cipher Block Chaining Mode Before encrypting of the sequent block, the result of previous block was XORed to the plaintext: Advantage: one block of ciphertext depends on all previous plaintext no repeats in ciphertext

Cipher and Outbut Feedback Modes Cipher Feedback Mode and Output Feedback Mode is the situations where there s some kind of feedback is organized for a cipher feedback mode the feedback loop involves both block cipher block and XORing for a output feedback mode the feedback loop involves only the cipher block which is recurrently started from a certain value (using initial key)

Output Feedback Mode

Using of Different Modes The most convenient but not sufficiently secure for a long plaintexts is an electronic codebook mode each bit of a ciphertext depends only on one plaintext block The most-of-used and sufficently secure mode is a cipher block chaining mode each bit of a ciphertext depends on all previous plaintext Feedback modes are less frequently used but they allow to use a block cipher as a stream cipher in order to produce the key sequence. Main usage area of them is secure erasing of a data from any rewritable media (disks, flash memory etc).

Inner Structure of a Block Cipher Block cipher block usually involves a numerous subsequent similar standard transformations of a plaintext called rounds (raund). Output of a previous round is an input to the next round How differents rounds use (generally different) keys is determined by a key sequence algorithm (v tmejaotusalgoritm). Key sequence algorithm may also be missing, in these cases all rounds use straightly the original key If such a key sequence algorithm exists, it comuptes from initial key the special round keys (raundiv tmed) for different rounds

Inner Structure of a Block Cipher

Parameters of a Typical Block Cipher Lenght of a key Lenght of a block (sometimes is equal to keylenght, but sometimes it s not) Number of rounds (and sometimes also the number of different round types) Presence of key sequence algorithm Number of round keys (if key sequence algorithm exists, sometimes is equal to number of rounds sometimes it s not) Lenght of round keys (sometimes it is equal to initial key, sometimes it s not)

Main Basic Operations Inside the Rounds substitution (substitutsioon) replacing of original characters (letters) by another characters (letters) transposition or permutation (transpositsioon, permutatsioon) changing the order of characters (letters) Most of transformations inside the block cipher rounds are certain (usually complex) combinations of them

AES: a Story, I In 1977 DES was adopted as a commercial encryption standard inside U.S.. It spread during the next two decades in all around the world as a first de facto encryption standard DES was a block cipher, with a block lenght of 64 bits and keylenght 56 bits Was internationally standardized, available from FIPS PUB 46-s (last version was issued in 1999, it was valid until 2005)

AES: a Story, II In late 1990s DES was already weak because of short keylenght 56 bits. In these reasons there was started a competition of a new standard AES Initial conditions of AES it must be a block cipher with a block lenght at least 128 bits and with 3 different keylenghts - 128, 192 and 256 bits In 1997 NIST (National Insitute of Standards and Technology) was announced the competition of AES (Advanced Encryption Standard)

AES: a Story, III In 1998 NIST announced 15 candidates for the further investigation In 1999 there were five finalists announced: MARS, RC6, Rijndael, Serpent and Twofish In November 26th 2001 the Rjindael was announced as winner of AES competition. Since this time is has been widely known as AES and has spread in all around the world

AES: Main Facts Has three different versions with different strenght (with different key lenghts) Is a block cipher with a block lenght of 128, 192 or 256 bits cosequently Uses a key which lenght is equal to the block lenght - consequently 128, 192 or 256 bits Authors are Joan Daemen and Vincent Rijmen Belgium Has won in November 26th 2001 the AES Competition, before it was known as a Rijndael Was published on FIPS 197

AES: Technical Description For a 128-bit key involves 10 rounds, for a 192- bit key involves 12 rounds and for a 256-bit key involves 14 rounds Key sequence algorithm is missing (all rounds use straightly initial key) Each round consists of four subsequent different type of transforms: byte sub (asendusbaidi faas) shift row (ridade nihutuse faas) mix column (tulpade segamise faas) add round key (raundiv tme lisamise faas)

AES: Byte Sub Each byte of a text is replaced by a one big substitution (S-box):

AES: Shift Row Sequence of bytes in a text will be changed. For a 128-bit block by a scheme: ... for a 192-bit block by a scheme:

AES: Shift Row ... and for a 256-bit block by a scheme:

AES: Mix Column For an each 4-byte column the multiplying by a following 4 x 4 matrix modulo 28= 256 is used: Add Round Key The key material is added by an ordinary XOR operation

AES: General Scheme

AES: Cryptanalysis Exhaustive search needs to performe a 2128 to 2256operations it is clearly infeasible Effective cryptanalytic means are not known up to this time (the algorithm is practically secure) Authors of AES (Rjindael) have itself shown it for a most of cryptanalytic methods known in these times (in 1999)