Introduction to
cryptography
@secucrypt | cryptosec.org
Creative Commons Attribution-NonCommercial-NoDerivs
agenda
> historical overview
> symmetric cryptography
> asymmetric cryptography
> hash functions
> combined usages
> conclusion
historical overview
> 1500 BC, on the banks of the Tigris in Iraq: a clay tablet on which is written the coded recipe of a varnish
> 500 BC: the first known military use, the Spartan scytale, transposition cipher (permutation of letters)
> 5th century BC: encryption of religious texts by the Hebrews: ex. The Atbash code, inversion of the alphabet
- Hebrew alphabet: aleph -> tau, beth -> shin
- Occidental alphabet: A -> Z , B -> Y
> 50 BC: beginning of the mathematical codes. The Caesar code: a shift of 3 letters in the alphabet
These are examples of substitution ciphers
> ~ 5th century: the Kamasutra recommends, among other arts, the learning of Mlecchita-Vikalpa, the art of secret writing
> 9th century: the Arab scientist Al Kindi wrote the first treatise of cryptanalysis using frequency analysis.
In French, the letter "e" being the most used, the substitution of "e" too (a countermeasure consisted in using lipograms)
> 1379: Gabriel de Lavinde publishes "The nomenclator", a collection of codes for the usage of diplomats
> 1467: Leon Battista Alberti proposes to use several mixed alphabets, introducing polyalphabetic codes. Goal: to counter the analysis of the frequencies. He build a cypher wheel, helping to use this figure
> 1553: for the polyalphabetic encryption, Giovanni Batista Bellaso proposes the use of literal keys which he calls "passwords"
1586, Vigenère cipher
> In 1864 Charles Babbage breaks the Vigenère code, thanks to a search of the length of the key and then an analysis of frequencies
Kerckhoffs's principles [1/2]
> Design principles for military ciphers published by August Kerckhoffs in "La cryptographie militaire" in 1883.
1. The system must be practically, if not mathematically, indecipherable
2. It should not require secrecy, and it should not be a problem if it falls into enemy hands
3. It must be possible to communicate and remember the key without using written notes, and correspondents must be able to change or modify it at will
Kerckhoffs's principles [2/2]
4. It must be applicable to telegraph communications
5. It must be portable, and should not require several persons to handle or operate
6. Lastly, given the circumstances in which it is to be used, the system must be easy to use and should not be stressful to use or require its users to know and comply with a long list of rules
> As opposed to "security through obscurity"
> Claude E. Shannon's motto: “The enemy knows the system”
(Wikipedia's translation)
Enigma
> World War II: Enigma, an electro-mechanical cipher machine invented by Arthur Scherbius and improved by the German army
> Polyalphabetic substitutions
> Higher complexity, but same kind of cipher than Vigenère
Enigma
> Enigma's cipher was broken during the war, with the help "bombes", electro-mechanical machines designed at Bletchley Park, based on an initial idea of Marian Rejewski
Back to the past - Linear A
"Linear A" is an undeciphered writing, probably originating from Crete - Minoan civilization, around 2000 - 1450 B.C.
Open questions!
- M. C. Escher -
Open questions
What mathematician played a key role in British efforts to break Enigma at Bletchley Park?
Who created PGP?
Who designed the algorithms Blowfish, Twofish and has the same first name than 李振藩 ?
« In crypto we trust » is the motto for...?
Turning point: 1976
> Whitfield Diffie and Martin E. Hellman publish a paper called « New directions in cryptography » where they propose the first asymmetric / public key algorithm.
Mention of the 2nd Kerckhoffs's principle, as opposed to security through obscurity:
> "In all cases it is assumed that the opponent knows the general system in use since this information can be obtained by studying a cryptographic device."
(https://ee.stanford.edu/~hellman/publications/24.pdf)
> In France, crypto was considered as a weapon of war until 1990 and strongly regulated until 1999
Open questions!
- M. C. Escher -
from itertools import starmap, cycle
key = 'define()'
def encrypt(message):
# convert to uppercase.
# strip out non-alpha characters.
message = filter(str.isalpha, message.upper())
# single letter encrpytion.
def enc(c,k): return chr(((ord(k) + ord(c) - 2*ord('A')) % 26) + ord('A'))
return "".join(starmap(enc, zip(message, cycle(key))))
def decrypt(message):
# single letter decryption.
def dec(c,k): return chr(((ord(c) - ord(k) - 2*ord('A')) % 26) + ord('A'))
return "".join(starmap(dec, zip(message, cycle(key))))
from itertools import starmap, cycle
key = 'THIS_IS_THE_SECRET_KEY'
def encrypt(message):
# convert to uppercase.
# strip out non-alpha characters.
message = filter(str.isalpha, message.upper())
# single letter encrpytion.
def enc(c,k): return chr(((ord(k) + ord(c) - 2*ord('A')) % 26) + ord('A'))
return "".join(starmap(enc, zip(message, cycle(key))))
def decrypt(message):
# single letter decryption.
def dec(c,k): return chr(((ord(c) - ord(k) - 2*ord('A')) % 26) + ord('A'))
return "".join(starmap(dec, zip(message, cycle(key))))
Vocabulary [1/2]
> Cryptography: Practice and study of techniques for secure communication in the presence of third parties called adversaries
> Cryptanalysis: Try to find weaknesses in a cryptographic scheme
> Encryption: converting ordinary information (called plaintext) into unintelligible text (called ciphertext)
> Decryption: Is the reverse, moving from the unintelligible cipher text back to plaintext
Vocabulary [2/2]
> Steganography: Practice of concealing a file, message, image, or video within another file, message, image, or video.
> Misc: Integrity, confidentiality, authentication, digital signature, non-repudiation...
Symmetric-key cryptography
Symmetric-key algorithms
> Reducing a "long" secret (the plaintext) into a "short" secret (the key)
> The key used to encrypt is the key used to decrypt
Symmetric-key algorithms
> Most of symmetric-key algorithms implement complex series of:
- Substitutions (units of plaintext are replaced by other units)
- Transpositions (units of the plaintext are rearranged, shifted according to a regular system)
> Symmetric-key algorithms are usually designed:
- To be fast (MB/s for 3-DES, several dozens of MB/s for RC4)
- To be easily implemented on electronic circuits (selection criteria for DES and AES)
Symmetric-key algorithms: samples [1/2]
> Lucifer, early 70's
> DES (Data Encryption Standard), 1977. 56-bit key. 3-DES: 64-bits blocks, 112 to 168 bits key
> IDEA, 1991. 64-bit blocks, 128-bit key
> CAST, 1996. 64-bit blocks, 128-bit or 256-bit key. Former AES candidate. RFC 2144 & 2612
> AES (Rijndael), 2000: 128-bit blocks, possible key sizes: 128, 192, 256 or 512 bits
> RC4, 1997. Stream cipher, fast, variable key size (up to 2048 bits). Multiple vulnerabilities were found
Symmetric-key algorithms: samples [2/2]
> RC5, 1994. 32, 64 or 128-bit blocks (64 suggested), up to 2040-bit key (128 suggested)
> RC6, 1998. 128-bit blocks, key sizes can be 128, 192, or 256-bit. AES finalist
> Blowfish, 1993. 64-bit blocks, key sizes 32–448 bits
> Twofish, 1998. 128-bit blocks, possible key sizes 128, 192 or 256. AES finalist
> One-time pad, 1882. XOR... Only cipher to provide perfect secrecy, but with a *long* key. Used for instance for "red telephone" encryption
Open questions!
- M. C. Escher -
Open questions
What are the problems of the One-time pad cipher?
If you have an encrypted text and some expected plaintext, and you try to brute-force the system in order to find the key which is k bits long, how many attempts do you need?
In average you will find the key after how many attempts?
In 2017, what is the recommended symmetric key size?
Block ciphers - Feistel networks
Block ciphers - Modes
> ECB (Electronic CodeBook), CFB (K-bit Cipher FeedBack), CBC (Cipher Block Chaining)...
Block ciphers - DES
> DES - Data Encryption Standard - 1977, NIST standardized
> Derived from Lucifer, created by Horst Feistel (& team) from IBM, first block cipher (128 bits keys and blocks, 16 rounds)
> DES was developed to be hardware-implemented - 64-bit blocks, 56-bit keys, Feistel network
> NSA reduces keys from 112 to 56, but also protected it against differential cryptanalysis
> DES 56 can be broken: EFF in 1998, "DES cracker", 3 days. In 1999, "DES cracker" + distributed.net (100 000 PC’s) 22h and 15mn
Block ciphers - DES
Block ciphers - DES
> No major weakness, brute force
> More reliable variant: triple DES
- Encrypt - Decrypt - Encrypt
- 3 different keys
- Resulting key: 112 bits
- But quite slow
Symmetric-key algorithm - IDEA
> IDEA - International Data Encryption Algorithm: from Switzerland (Xuejia Lai / James Massey), 1990-1992
> 64-bit blocks, 128-bit key size
> Almost as fast than DES-56
> Used for example in PGP, SSH, OpenSSL
> Over the years, some weaknesses appeared
> Its successor is IDEA NXT / FOX
Symmetric-key algorithm - AES
> As DES was becoming old, NIST launched in 1997 an international call for proposals for selecting the new Advanced Encryption Standard
> 5 finalists were:
- MARS, from IBM
- RC6, from RSADSI
- Rijndael, from Joan Daemen & Vincent Rijmen
- Serpent, from Anderson, Biham & Knudsen
- Twofish, from Bruce Schneier
Symmetric-key algorithm - AES
> In 2000, winner was announced: Rijndael
- Very fast, on hardware as well as on software
- 128-bit blocks, key size of 128, 192 or 256 bits
- Becomes de facto the replacement for DES
> AES is at least 2,7 faster than 3-DES (which is 3 times slower than DES)
> No known weaknesses
Symmetric-key algorithm - Limits
n*(n-1)/2 secrets for n users
10 users: 45 keys
100 users: 4950 keys
5 000 users: 12 497 500 keys
Symmetric-key algorithm - Conclusion
> Advantages of symmetric-key aglorithms
- fast
- robust
- algorithmic simplicity
> Limits of symmetric-key encryption
- number of keys
- sharing keys (no way to establish a secured channel with an unknown third party)
Asymmetric cryptography
Asymmetric cryptography
> A solution to symmetric key crypto problems: distribution of symmetric keys and impossibility of establishment of shared keys
> Based on mathematical asymmetries: usage of mathematical functions which are not easy to inverse
Asymmetric-key algorithm - Diffie-Hellman
In 1976, Whitfield Diffie and Martin Hellman propose a new concept, based on public and private keys:
> Mainly used to establish shared keys without sharing secrets, but also for signatures
> Security relies on difficulty (slow) to compute discrete logarithms vs. easiness to compute exponentials
> Can be extended to more than 2 participants
> Used in protocols like TLS, IPSec...
> It is now known that James H. Ellis, Clifford Cocks, and Malcolm Williamson (UK) did significant work on asymmetric algorithms, but their discoveries remained classified
Asymmetric-key algorithm - Diffie-Hellman
The algorithm:
Alice and Bob want to establish a shared symmetric key without exchanging any secret.
> They agree on two large integers without common factor, n and g
> Bob chooses a large random integer x, and computes: X = g^x(mod n) and sends it to Alice
> Alice chooses a large random integer y, and computes: Y = g^y(mod n) and sends it to Bob
> Bob computes k = Y^x(mod n)
> Alice computes k' = X^y(mod n)
> k = k' = g^xy(mod n)
Alice and Bod managed to establish a shared secret key without exchanging any secret
Open questions!
- M. C. Escher -
Open questions
Calculate mentally
23 x 31
(rise hand when finished)
Factorize
481
(rise hand when finished)
Conclusion?
Asymmetric-key algorithm - RSA
> 1977, by Ron Rivest, Adi Shamir & Leonard Adleman
> RSA is the most used asymmetric algorithm:
- 100 to 1000 times slower than DES (soft or hard)
- Security relies on the difficulty to factorize large integers into prime factors
> Usages:
- Signature
- Encryption
- Key exchanges
Asymmetric-key algorithm - RSA
> A public key, a private key
> Private key: sign and decrypt
> Public key: verify and encrypt
> Signature verification is much faster than the generation of a signature
Asymmetric-key algorithm - RSA
> Fermat's little theorem:
If p is prime and a is not a multiple of p, then:
a^(p-1) = 1(mod p)
i.e.: a^p - a is a multiple of p
> Samples:
5^3 - 5 = 120 is divisible by 3
2^97 - 2 = 158 456 325 028 528 675 187 087 900 670 is divisible by 97
Asymmetric-key algorithm - RSA
Euler continues Fermat's work
In 1763, "Euler's theorem":
If "n" is a positive integer and "a" an integer prime with "n", then:
a^f(n) = 1 (mod n) where f(n) = (p-1)(q-1)
RSA is based on this theorem
Asymmetric-key algorithm - RSA
Alice wants to communicate securely with Bob:
Alice chooses 2 large prime integers: p and q (with a probabilistic primality test)
She computes n = p.q
She chooses an integer e which is prime with (p-1)(q-1)
(e,n) is the public key (n gives the lenght of the RSA key)
She chooses d so that e.d = 1 (mod (p-1)(q-1)) (extended Euclidean algorithm)
(d,n) is the private key
Asymmetric-key algorithm - RSA
Bob wants to send an encrypted message to Alice:
> Sending of the encrypted message
- Message is represented by one or several integers M, such as 0 < M < n-1
- Bob has Alice's public key, (n,e). He computes: C = M^e (mod n)
- Bob sends C to Alice
> Reception and decryption of the message
- Alice computes D = C^d (mod n)
- D = M^ed (mod n) = M^[k(p-1)(q-1)+1] (mod n) = M.M^[k(p-1)(q-1)] (mod n)
- D = M^ed (mod n) = M (mod n)... which is the original message.
Asymmetric-key algorithm - RSA
> RSA's security relies on the difficulty to solve a mathematical problem: depends on maths and computational progress
> 22 august 1999, a 512-bit number factorised in 5.2 month - 37,5 years CPU at 8 000 MIPS
> In 2009, RSA-768 factorised (232 digits)
> Recommended key-size in 2017: not less than 2048 bits
Asymmetric-key algorithm - DSA
> Designed by US agencies and NSA and adopted as digital signature standard (DSS) in 1994
- Variation of ElGamal, which itself is a variation of Diffie-Hellman, based on discret logarithm
- Optimised for signature but can be used for encryption
- Keys > 1024 bits
- Signature creation faster than signature verification
Asymmetric-key algorithm - Elliptic curves (ECC)
> Middle 80'
- Another way to implement discret logarithm
- Points on elliptic curves which form a group where arithmetic operations can be done
- For an equivalent security, keys are shorter
- ANSI / IEE / NIST standardisation: ECDSA
- Very common nowadays
> Advantages: Shorter keys | Adapted for systems with low resources (smartcards, tokens, etc.)
> Disadvantages: Still young | Development was restrained by patents
Asymmetric-key algorithm - sum up
> A key pair
- a public key: to be widely distributed
- a private key: to be kept secret
> What is encrypted with the public key can only be decrypted with the private key
> What is encrypted with the private key can only be decrypted with the public key
> It is impossible to guess a private key from the public key
Asymmetric-key algorithm - limits and advantages
> Limits
- slow... ~1000 slower than symmetric algorithms
- security relies on a lot of mathematical assumptions
- algorithm complexity
> Advantages
- number of keys
- public key exchange very easy
- accountability of actions
Open questions!
- M. C. Escher -
Open questions
What are the usages of asymmetric algorithms?
> Identification / Authentication
- associate a person, a resource, with a digital identity
- certainty about identities
> Confidentiality / Encryption
- data protection
- data only readable by the desired recipient
> Integrity / Digital signature
- impossibility to alter data without detecting it
> Non-repudiation
- if someone signs, he can't deny he signed
Hashing algorithms
Hashing algorithms - Principles
> Goal: provide fingerprints of arbitrary data, unique and of a fixed length:
- must be irreversible
- should be impossible to find initial data which as a given hash as a result
- should be impossible to find two different initial texts which have the same hash
Hashing algorithms - Principles
> Other properties:
- the link between the data and the fingerprint should appear as random as possible
- a minimal modification of the initial data should completely modify the fingerprint
- hashing algorithms must be fast
> Usages:
- signature process - integrity: reduction of the amount of data to sign
- MAC (Message Authentication Code) and HMAC
Hashing algorithms - Samples
> Old ones:
- MD2, MD4, no more used, have known weaknesses
> Common, but to avoid:
- MD5 (Message Digest Algorithm 5), hash length 128 bits, weaknesses have been found
- SHA-1 (Secure Hash Algorithm), hash length 160 bits, weaknesses have been found
> The new ones:
- RIPEMD-160 (replacement of MD4 et MD5), hash length 160 bits
- SHA-256 (replacement of SHA-1), hash length 256 bits
Combined usages
Combined usages
> Encryption :
- usage of asymmetric algorithms to exchange an encryption key
- usage of symmetric algorithms with the exchanged key to encrypt communication
> Easy asymmetric key exchange, fast symmetric encryption
Combined usages: Encryption
Combined usages: Digital signature
Open questions!
- M. C. Escher -
Open questions
Which key-length would you recommend for AES, RSA, ECC, SHA?
What is letsencrypt.org ?
How to detect if there is a Man-in-the-Middle in a TLS connexion?
Open questions
Conclusion
Conclusion - Bibliography
Secrets et mensonges, Sécurité numérique dans un monde en réseau, de Bruce Schneier, éditions Vuibert Informatique.
La signature électronique, Transactions et confiance sur Internet, de Arnaud-F. Fausse, éditions Dunod.
Sécuriser ses échanges électroniques avec une PKI, de Thierry Autret, Laurent Bellefin et Marie-Laure Oble-Laffaire, éditions Eyrolles.
Digital Certificates, de Jalal Feghhi, Jalil Feghhi et Peter Williams, éditions Addison Wesley.
Initiation à la Cryptographie, de Gilles Dubertet, éditions Vuibert.
Cryptographie, théorie et pratique, de Douglas Stinson, éditions Thomson Publishing.
Cryptographie Appliquée, de Bruce Schneier, éditions Thomson Publishing.
Algorithmique et cryptographie, de Guy Robin, éditions Ellipses.
Cours de cryptographie, de Gilles Zémor, éditions Cassini.
Cryptography and Network Security, de William Stallings, éditions Prentice Hall.
Internet, Sécurité et Firewalls, de Karanjit Siyan et Chris Hare, éditions Mc Millan.
L’Ethique Hacker et l’esprit de l’ère de l’information, de Pekka Himanen, édition Exils.
Histoire des codes secrets, Simon Singh, éditions JC Lattès.
Enigma, de Robert Harris, éditions Pocket.
Conclusion - The *easy* slide
> Cryptography is for specialists, but we must know the basics
> I want to stay informed?
@schneierblog | www.schneier.com/crypto-gram
> No time... I only want to know which key-length using...
> ... Do you have configurations I could copy-past?
Conclusion - Next?
Cryptographic formats and protocols, Quantum cryptography...
¡ Thank you !
Twitter: @secucrypt
cryptosec.org