- references
- https://stackoverflow.com/a/72461285
- https://stackoverflow.com/questions/33105434/converting-a-base10-number-to-a-basen-number-using-a-custom-alphabet-of-size-n
- https://gist.github.com/jasperdenkers/59cf5ad4acbba6b9d75d
- https://crypto.stackexchange.com/questions/81495/rsa-is-there-a-way-to-digitally-sign-a-message-without-knowing-the-private-key
- https://www.johndcook.com/blog/2019/03/06/rsa-exponent-3/
- https://stackoverflow.com/questions/1967578/how-bad-is-3-as-an-rsa-public-exponent
- https://crypto.stackexchange.com/questions/3608/why-is-padding-used-for-rsa-encryption-given-that-it-is-not-a-block-cipher
- https://crypto.stackexchange.com/questions/22531/how-does-rsa-padding-work-exactly
- https://www.encryptionconsulting.com/education-center/what-is-rsa/
- https://www.comparitech.com/blog/information-security/rsa-encryption/
- Faster Primality Test - Applied Cryptography
- https://en.wikipedia.org/wiki/Carmichael_number
- How To Tell If A Number Is Prime: The Miller-Rabin Primality Test
- https://blog.trailofbits.com/2019/07/08/fuck-rsa/
- https://en.wikipedia.org/wiki/Carmichael_number
- https://medium.com/@prudywsh/how-to-generate-big-prime-numbers-miller-rabin-49e6e6af32fb
- Cipher Block Chaining
- Encrypting with Block Ciphers
- https://www.techtarget.com/searchsecurity/definition/cipher-block-chaining
- https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation
- Devoxx Greece 2024 - Asymmetric Cryptography: A Deep Dive by Eli Holderness
- https://chatgpt.com/
- only for workshop purposes
- for example: given implementation of RSA does not have padding
- goals of this workshop
- introduction to asymmetric cryptography
- mathematical basis for asymmetric cryptography
- understanding purpose of trapdoor functions
- introduction to RSA
- common vulnerabilities
- some basic attacks
- basics of padding
- basic knowledge of block ciphers
- structure
- package cryptography
- decryption/encryption
- signing/signature verification
- package key - to generate RSA key pair: private and public
- package prime - generating primes
- exploits are shown in RsaExploitsTest
- package cryptography
- all used/needed math is described here: https://github.com/mtumilowicz/cryptography-math-basics
- solve the problem of secure communications over an insecure network
- symmetric cryptography context
- to exchange messages => first mutually agree on a secret key k
- what if every communication is monitored?
- is it possible to exchange a secret key?
- first reaction: not possible
- reason: every piece of information is public
- solution: public key (or asymmetric) cryptography
- first reaction: not possible
- is it possible to exchange a secret key?
- what if every communication is monitored?
- asymmetric ciphers - slower than symmetric ciphers
- first use an asymmetric cipher to send the key to a symmetric cipher
- then use symmetric key to transmit the actual file
- to exchange messages => first mutually agree on a secret key k
- analogy
- Alice: buys a safe with a narrow slot in the top and puts it in a public location
- Bob: writes his message and slips it through the slot
- Alice: only a person with the key to the safe can retrieve Bob’s message
- summary
- public key: the safe
- encryption algorithm: putting the message in the slot
- decryption algorithm: opening the safe with the key
- mathematical formulation
- three sets
- keys K
- k = (kpriv, kpub) // private key and the public key
- plaintexts M
- ciphertexts C
- keys K
- for each kpub => exists encryption function e_kpub: M -> C
- for each kpriv => exists decryption function d_kpriv: C -> M
- (kpriv, kpub) e K => (d_kpriv) o (e_kpub) is identity on M
- private key is sometimes called trapdoor information
- it provides a trapdoor (shortcut) for computing the inverse function of e_kpub
- it must be difficult to compute inverse function of e_kpub without a trapdoor information
- it provides a trapdoor (shortcut) for computing the inverse function of e_kpub
- private key is sometimes called trapdoor information
- encryption is a permutation of b-bit strings
- {0, 1}^b -> {0, 1}^b
- each key "chooses" some permutation
- three sets
- is a function that
- is easy to compute in one direction
- believed to be difficult to find its inverse (without special information, called the "trapdoor")
- analogy: padlock and its key
- it is trivial to change the padlock from open to closed without using the key
- opening the padlock easily requires the key to be used
- key is the trapdoor
- example
- set some n, and define function as y = x^e mod n
- bad trapdoor function
- n = p (prime)
- y = x^e mod p
- we have to find inverse of e mod (p - 1)
- Fermat's little theorem => we can perform calculations mod (p − 1) in the exponent
- ed = 1 mod (p - 1)
- it is solvable (for example using extended Euclidean algorithm) if gdc(e, p-1) = 1
- y^d = (x^e)^d = x^ed = x mod p
- solution is unique
- suppose that we have two solution c1, c2
- c1 ≡ c1^de ≡ (c1^e)^d ≡ y^d ≡ (c2^e)^d ≡ c2^de ≡ c2 mod p
- summary: very easy to reverse
- good trapdoor function (rsa)
- n = pq, p,q - prime
- y = x^e mod n
- we have to find inverse of e mod φ(pq)
- Euler's theorem => we can perform calculations mod φ(pq) in the exponent
- ed = 1 mod φ(pq)
- it is solvable (for example using extended Euclidean algorithm) if gdc(e, φ(pq)) = 1
- however, calculating φ(pq) is as hard as factoring pq
- d - decryption exponent
- e - encryption exponent
- solution is unique
- c1 ≡ c1^de ≡ (c1^e)^d ≡ y^d ≡ (c2^e)^d ≡ c2^de ≡ c2 mod n
- if we know the actual factors, we can use Euler’s theorem and write x as
- x = y^d mod n
- ed = 1 mod (p-1)(q-1)
- bad trapdoor function
- set some n, and define function as y = x^e mod n
- asymmetric encryption algorithm
- named after its inventors: Ron Rivest, Adi Shamir, and Leonard Adleman
- rsa = good trapdoor function explained above (product of two large prime numbers)
- encryption is faster if e is small and decryption is faster if d is small
- most common e is 65537
- we are encrypting / decrypting numbers - not letters
- example
- encrypting: "hello"
- observation: all of the information is already stored in binary
- encoding standards like ASCII or Unicode are used for humans to understand
- this means that "hello" already exist as number
- example
- RSA relies on the size of its key to be difficult to break
- longer RSA key => more secure it is
- prime generating problem
- how to test a given number n for being prime?
- maybe use Fermat’s little theorem?
- take A: gcd(A,n) == 1
- if A^(n−1) ≠ 1 mod n => then n is composite
- otherwise, it is prime with some probability
- repeat for many As to increase the likelihood of being prime
- if A^(n−1) ≠ 1 mod n => then n is composite
- why it's wrong?
- take n = 561
- this is composite number and fulfills Fermat's theorem for any A
- family of such numbers are called Carmichael numbers
- take n = 561
- take A: gcd(A,n) == 1
- Miller Rabin primarity test
- let p be an odd prime
- p−1 = 2^k q, gcd(a,p)=1 => one of the following two conditions is true
- a^q is congruent to 1 modulo p
- q = p-1 / 2^k
- one of a^q, a^2q , a^4q ,..., a^2^(k−1)q is congruent to −1 modulo p
- a^q is congruent to 1 modulo p
- proof
- n = 2^k * q + 1
- a^(n-1) = 1 mod n
- a^(n-1) - 1 = 0 mod n
- (a^(n-1 / 2) - 1)(a^(n-1 / 2) + 1) = 0 mod n
- (a^(n-1 / 4) - 1)(a^(n-1 / 4) + 1)(a^(n-1 / 2) + 1) = 0 mod n
- (a^(n-1 / 2^k) - 1)(a^(n-1 / 2^k) + 1)...(a^(n-1 / 2) + 1) = 0 mod n
- we can expand it until n-1 / 2^k is odd
- if n divides at least one multiplier => probably prime
- Euclid's lemma: if p prime <=> p|ab => p|a or p|b
- so we check this one by one
- each number in the list is the square of the previous number
- n-1 / 2^k, n-1 / 2^(k-1), n-1 / 2^(k-2)
- if n is composite then running k iterations of the Miller–Rabin test will declare n probably
prime with a probability at most 4^(−k)
- proof
- prime number density
- φ(n) is the number of prime numbers ≤ n
- prime number theorem states that n / ln(n) is a good approximation of φ(n)
- it means the probability that a randomly chosen number is prime is 1 / ln(n)
- there are n positive integers ≤ n
- approximately n / ln(n) primes
- n / ln(n) / n = 1 / ln(n)
- probability to find a prime number of 1024 bits: (ln(2¹⁰²⁴)) = (1 / 710)
- primes are odd (except 2), we can increase this probability by 2
- to generate a 1024 bits prime number, we have to test 355 numbers randomly generated
- maybe use Fermat’s little theorem?
- how to test a given number n for being prime?
- elliptic curves cryptography pros over rsa
- smaller key sizes and signatures
- example
- 256-bit ECC key ~ 3072-bit RSA key
- 384-bit ECC key ~ 7680-bit RSA key
- lower storage requirements for both private keys and public keys
- example
- less computational power for key generation, encryption, and decryption
- valuable for low-power devices such as IoT devices and mobile phones
- smaller key sizes and signatures
- structure of a message can give attackers clues about its content
- padding: adding randomized data to hide the original formatting
- using the word padding for RSA is by now rather incorrect
- RSA without padding is also called Textbook RSA
- old padding schemes for RSA did simply extend the message before converting a number
- newer schemes actually alter the message itself as well
- example: OAEP
- entire message is randomly transformed before RSA modular exponentiation
- the same message encrypted multiple times looks different each time
- example: OAEP
- using the word padding for RSA is by now rather incorrect
- padding oracles
- adding padding to a message requires the recipient to perform an additional check whether the message is properly padded
- when the check fails, the server throws an invalid padding error
- that single piece of information is enough to slowly decrypt a chosen message
- process is tedious and involves manipulating the target ciphertext millions of times
- isolating the changes to get valid padding
- that one error message is all you need to eventually decrypt a chosen ciphertext
- it makes developing secure libraries almost impossible
- padding oracle attack
-
if block ciphers act on short blocks, how do we encrypt a long message?
- electronic codebook mode (ECB)
- encrypt each block separately
- example
- codebook
- 00 -> 11
- 01 -> 00
- 10 -> 01
- 11 -> 10
- plaintext: 00|11|00|01|00
- cipher: 11|10|11|00|11
- codebook
- cons
- patterns
- cipher block chaining (CBC)
- each block of plaintext is XORed with the previous ciphertext block before being encrypted
- cipher block chaining uses what is known as an initialization vector (IV) of a certain length
- pros
- decryption of a block of ciphertext to depend on all the preceding ciphertext blocks
- electronic codebook mode (ECB)
-
summary
- TLS 1.3 no longer supports RSA
- criticism: https://www.youtube.com/watch?v=lElHzac8DDI
- using prime factorization, researchers managed to crack a 768 bit key RSA algorithm
- recommendations: a minimum key length of 2048 bits now
- many organizations have been using keys of length 4096 bits
- recommendations: a minimum key length of 2048 bits now
- p and q must be globally unique
- if p or q ever gets reused in another RSA moduli => can be easily factored using the GCD algorithm
- RSA primitive is based on modular exponentiation
- this operation is homomorphic
- c1=md1, c2=md2 => (m1m2)^d=c1c2=c
- to fix it - it is the essential to break this "homomorphism"
- padding
- example: RsaExploitsTest "sign then verify - product attack"
- small exponent
- for example: 3 // most common exponent is 65537
- suppose you’re using a 2048-bit modulus N and exchanging a 256-bit key
- message m is simply the key without padding => m³ < N => take the cube root
- example: RsaExploitsTest "encode / decode - e < n"
- solves a problem analogous to the purpose of a pen-and-ink signature on a physical document
- assymetric cryptography vs digital signatures
- consider an analogy: bank deposit vaults vs signet rings
- in today’s world signet rings and wax images obviously would not provide much security
- consider an analogy: bank deposit vaults vs signet rings
- digital signatures are at least as important as public key cryptosystems
- significant use-case
- your computer receives program and system upgrades over the Internet
- how can your computer tell that an upgrade comes from a legitimate source?
- example: the company that wrote the program?
- solution: digital signature
- original program comes equipped with the company’s public verification key
- company uses its private signing key to sign the upgrade
- your computer can use the public key to verify the signature before installing it on your system
- it is quite inefficient to sign a large digital document D
- it takes a lot of time to sign each b bits of D
- resulting digital signature ~ as large as the original document
- solution: use a hash function
- hash: (arbitrary size documents) -> {0,1}^k
- it should be very difficult to find D and D' whose hash(D) and hash(D') are the same
- rather than signing document D sign the hash hash(D)
- for verification: compute and verify the signature on hash(D)
- hash: (arbitrary size documents) -> {0,1}^k
- setup
- the same as for RSA encryption
- encryption
- e = encryption exponent
- d = decryption exponent
- signing
- d = signing exponent
- sign document D by computing S ≡ D^d (mod N)
- e = verification exponent
- compute S^e mod N and verify that it is equal to D
- d = signing exponent