Crypto 102: How to break crypto in practice

Batman’s Kitchen 2025 | Dhruv Ashok

“There are tens, probably hundreds, of obscure little things you can do to take a cryptosystem that should be secure even against an adversary with more CPU cores than there are atoms in the solar system, and make it solvable with a Perl script and 15 seconds.” - Cryptopals

Review/Preliminaries

Crypto 101 Recap

• Symmetric crypto
• Both parties use a shared key
• AES, ChaCha20, DES
• Asymmetric crypto
• Both parties have a public/private keypair
• RSA, Diffie Hellman, Elliptic Curves

Trapdoor functions

• Some computation that is (reasonably) efficient to compute one way, but practically impossible the other way without the right information
• All public-key cryptosystems need something like this
• Allows us to mathematically “link” the public and private key
• But prevents someone from deriving the private key from the public key, for example

Modular arithmetic

• Do your computation, then take the remainder of what you’d get if you divided it by the modulus
• 2*3 (mod 5) = 1
• All your computations sort of “cycle back around”
• Basis for a lot of the asymmetric crypto stuff we’ll talk about today

Asymmetric cryptosystems

RSA (keygen)

• Pick two large primes, say p and q
• Let N = p*q, and let ɸ(N) = (p-1)*(q-1)
• Now, pick an integer e such that e < ɸ(N) and gcd(e, ɸ(N)) = 1
• The pair (N, e) is our public key
• To get the corresponding private key
• Let d ≣ e^-1 (mod ɸ(N))
• Find e such that d*e ≣ 1 (mod ɸ(N))
• The pair (ɸ(N), d) is our private key

RSA ({en,de}cryption)

• Encryption
• Let m < N be our message
• Let c = m^e (mod N) be our ciphertext

​

• Decryption
• Let c < N be our ciphertext
• Let m = c^d (mod N) be our recovered plaintext

RSA (proof of correctness)

First, c^d = (m^e)^d = m^{e*d}. Now, consider that since e*d ≣ 1 (mod ɸ(N)), we have by modular arithmetic that e*d = 1 + k*ɸ(N) for some positive integer k. It follows that m^{e*d} = m^{1 + k*ɸ(N)} = m^1 * m^{k*ɸ(N)} = m * (m^{ɸ(N)})^k. Now, recall that by Fermat’s Little Theorem, since m is coprime to ɸ(N), it follows that m^{ɸ(N)} ≣ 1 (mod N). Hence, m * (m^{ɸ(N)})^k = m * 1^k = m, completing the proof.

RSA: CTF example 1 (small N)

• What happens if we can factor N?
• Generally, you can do this if N is 512 bits or less (note that if it’s 512 bits you’ll need a lot of compute though)
• Always check https://factordb.com/
• Compute factors p, q such that p*q = N
• Compute ɸ(N) = (p-1)*(q-1)
• Compute d ≣ e^{-1} (mod ɸ(N))
• Recover m ≣ c^d (mod N)

RSA: CTF example 2 (bad prime selection)

• https://dhruvashok.github.io/2022/11/19/hardcopy.html
• Should never pick primes that are too close together as they are vulnerable to Fermat’s attack
• More generally, avoid any relation between the primes you pick
• Easiest way is to just do like p := randPrime(1024) and q := randPrime(1024)

RSA: further attacks

• Decryption oracle
• Small value of e (i.e., e = 3)
• Defeated via Coppersmith’s Attack
• Uses lattices
• To avoid this, use e = 65537
• Small d (Wiener’s attack) (yes, it’s really called that)
• Uses some relation between public parameters and private parameters and continued fractions
• 20 Years of Attacks on RSA: https://www.ams.org/notices/199902/boneh.pdf
• There’s a lot of ways you can go wrong

​

RSA: signature scheme

• As an aside, you can get a signature scheme out of RSA too
• Sign using your private key d
• Let H(m) be the hash of the message you’re signing
• The signature S is then H(m)^d, where d is your private key
• Verify using your public key e
• Let H(m) be the hash of the message you’re verifying the signature on
• Compute H’ = S^e
• Output whether H’ == H(m)
• The proof of correctness for this is basically the same as the decryption one

Diffie Hellman

• Key exchange protocol, NOT an encryption algorithm like RSA
• Remember the paint example?
• “Mixture separation” = discrete logarithm problem
• Let g be an integer (usually g=2 or g=3, or something)
• Let p be a large prime (~2048 bits)
• Choose a < p-1 (this is your private key)
• Compute A = g^a (mod p) (this is your public key)
• Given g and A = g^a, the DLP is the task of finding a
• This is the trapdoor problem (for well chosen parameters)

ECDH

• Same exact general idea as DH, we just use a different group now
• Don’t worry if you don’t know what a group is
• Instead of using the set of integers modulo a large prime, let’s use the set of points on an elliptic curve over a prime field (don’t worry if this makes no sense)
• It turns out that the ECDLP (elliptic curve analogue of the DLP) is even stronger for well-chosen parameters
• This allows us to use much smaller elements for ECDH than for DH and achieve the same security

(EC)DSA (and a cool attack on it I did)

• Much like RSA, you can also get a signature scheme out of this
• A lot of the modern internet uses ECDSA! (unfortunately, so does the blockchain)
• I won’t do details here, but will instead point you to this cool attack I did
• https://dhruvashok.github.io/2023/09/14/ecdsa-led-part1.html
• Basically, ECDSA has a lot of fun issues around the nonce that you use in it
• PS3’s root key (used to sign firmware) was computed due to one such issue

Symmetric cryptosystems

AES: ECB review

AES: CBC review

AES: PKCS7 Padding

• Plaintext gets split into blocks, needs to be aligned to the block size (usually 16) for this to work
• If the last block has size k and the block size is N, then we add N-k bytes of byte(N-k) to the end of our plaintext to pad it
• If our PT is “AA” and N = 4, then our padded PT would be “AA\x02\x02”
• An error will usually get thrown by your crypto library if you don’t follow this rule

AES: padding oracle attack on CBC

• Suppose a website encrypts their cookies with AES in CBC mode, storing the CT and IV
• You can modify the cookie; the server will decrypt whatever is in it each time you send a request
• In other words, you have a decryption oracle
• Depending on how verbose this server is with its errors, we may have a viable attack
• https://www.nccgroup.com/us/research-blog/cryptopals-exploiting-cbc-padding-oracles/
• ​

AES: bit flipping attack on CBC

• High-level is that you can flip bits of the IV that will directly flip what you get as your CT
• Works for first block, gets more dicey as you go to subsequent blocks
• This is because for N > 1, the IV for block N is the ciphertext block N-1
• So a flip in CT block N-1 will achieve the desired result for PT block N, but will corrupt PT block N-1

Authenticated Encryption

• The fundamental problem was that the server decrypted arbitrary data
• What if we add some form of integrity check so that the server verifies data before decryption?
• You can do this a few different ways
• Encrypt-then-MAC
• Encrypt like normal, add a MAC using something like HMAC
• When decrypting, verify the MAC first before decrypting
• AES-GCM (Galois counter mode, used widely on the internet)
• MAC is sort of built into the scheme
• This countermeasure essentially prevents the previous attacks
• You should generally always use authenticated encryption too

Crypto, modulo this talk (i.e., all the stuff not in this talk)

• Multiparty computation
• Post-quantum cryptography
• Privacy-preserving systems
• Side channel attacks
• Zero-knowledge proofs/verifiable computation
• And lots, lots, more…

Crypto 103 when?

Thank you!