<commit_before>---
layout: default
title: writeups/cryptopals3
category: pages
---

[matasano / cryptopals](http://www.cryptopals.com)

## Set 3 ##

### 17. The CBC padding oracle ###

The first function we have to create selects one of the 10 given strings at random, pads & encrypts with a random key. Nothing fancy here, except that as usual we need to store the IV and the key.

The 2nd function is our oracle:

{% highlight python %}
    RANDOM_AES_KEY = b'\<KEY>
    RANDOM_IV = b'\xa8\xe8\x9fO\xb0r\xb7F\xcd\xe8\x1f8\xba9\xa4\x0e'

    def padding_oracle(ciphertext, key=RANDOM_AES_KEY, iv=RANDOM_IV):
      from Crypto.Cipher import AES
      cr = AES.new(key, AES.MODE_CBC, IV=iv)
      dec = cr.decrypt(ciphertext)
      try:
        crypto_utils.unpad(dec) # we do an assert which throws if it fails
        return True
      except Exception as e:
        return False
{% endhighlight %}

Now comes the tricky bit (see References below). We'll start with the first 2 blocks only - `C1||C2`. Our aim is to modify `C1` - turning it into `C'1` such that when we pass `C'1||C2` to `padding_oracle` it returns True. That is, we end up with `P'2` such that the block 'unpads' nicely - which allows us to back out what `I2` should be, bypassing the decryption step entirely. We can then do `C1^I2` to get `P2`.


{% highlight python %}
    def mc_part17():
      (iv, enc) = p17_f1() # note this will be random every time we run this
      c1, c2 = enc[0:16],enc[16:32]
      # zero out c_1 and i_2
      c_1 = bytearray(b'\x00'*16)
      i2 = bytearray(b'\x00'*16)
      pad_byte = 1
      for j in range(15,-1,-1):
        for i in range(0,256):
          c_1[j] = i
          if padding_oracle( bytes(c_1 + c2) ):
            break
        # we know that i2[j]^c_1[j] = pad_byte so we can derive i2[j]
        i2[j] = c_1[j]^pad_byte
    
        # we need to set c_1 up for the next iteration
        # all bytes >= j must, when xor'ed with i2, show the right padding
        # we can do that because we now know i2 from j onwards
        pad_byte += 1
        for k in range(j,16):
          c_1[k] = i2[k]^pad_byte
    
      # we know i2 - we bypassed the decryption step entirely and can back out the plaintext
      p2 = crypto_utils.xor_bytearrays(c1, i2)
      print(p2)
{% endhighlight %}

For simplicity, the above only takes the first 2 blocks into account. Expanding this to cover all (adjacent) blocks should be trivial.

#### References ####

[skullsecurity](https://blog.skullsecurity.org/2013/a-padding-oracle-example) and <NAME>'s [blog](http://robertheaton.com/2013/07/29/padding-oracle-attack/). This small article on [padbuster](http://blog.gdssecurity.com/labs/2010/9/14/automated-padding-oracle-attacks-with-padbuster.html) is neat too.

### 18. Implement CTR, the stream cipher mode ###
### 19. Break fixed-nonce CTR mode using substitions ###
### 20. Break fixed-nonce CTR statistically ###
### 21. Implement the MT19937 Mersenne Twister RNG ###
### 22. Crack an MT19937 seed ###
### 23. Clone an MT19937 RNG from its output ###
### 24. Create the MT19937 stream cipher and break it ###<commit_msg>challenge 18<commit_after>---
layout: default
title: writeups/cryptopals3
category: pages
---

[matasano / cryptopals](http://www.cryptopals.com)

## Set 3 ##

### 17. The CBC padding oracle ###

The first function we have to create selects one of the 10 given strings at random, pads & encrypts with a random key. Nothing fancy here, except that as usual we need to store the IV and the key.

The 2nd function is our oracle:

{% highlight python %}
    RANDOM_AES_KEY = b'\<KEY>
    RANDOM_IV = b'\xa8\xe8\x9fO\xb0r\xb7F\xcd\xe8\x1f8\xba9\xa4\x0e'

    def padding_oracle(ciphertext, key=RANDOM_AES_KEY, iv=RANDOM_IV):
      from Crypto.Cipher import AES
      cr = AES.new(key, AES.MODE_CBC, IV=iv)
      dec = cr.decrypt(ciphertext)
      try:
        crypto_utils.unpad(dec) # we do an assert which throws if it fails
        return True
      except Exception as e:
        return False
{% endhighlight %}

Now comes the tricky bit (see References below). We'll start with the first 2 blocks only - `C1||C2`. Our aim is to modify `C1` - turning it into `C'1` such that when we pass `C'1||C2` to `padding_oracle` it returns True. That is, we end up with `P'2` such that the block 'unpads' nicely - which allows us to back out what `I2` should be, bypassing the decryption step entirely. We can then do `C1^I2` to get `P2`.


{% highlight python %}
    def mc_part17():
      (iv, enc) = p17_f1() # note this will be random every time we run this
      c1, c2 = enc[0:16],enc[16:32]
      # zero out c_1 and i_2
      c_1 = bytearray(b'\x00'*16)
      i2 = bytearray(b'\x00'*16)
      pad_byte = 1
      for j in range(15,-1,-1):
        for i in range(0,256):
          c_1[j] = i
          if padding_oracle( bytes(c_1 + c2) ):
            break
        # we know that i2[j]^c_1[j] = pad_byte so we can derive i2[j]
        i2[j] = c_1[j]^pad_byte
    
        # we need to set c_1 up for the next iteration
        # all bytes >= j must, when xor'ed with i2, show the right padding
        # we can do that because we now know i2 from j onwards
        pad_byte += 1
        for k in range(j,16):
          c_1[k] = i2[k]^pad_byte
    
      # we know i2 - we bypassed the decryption step entirely and can back out the plaintext
      p2 = crypto_utils.xor_bytearrays(c1, i2)
      print(p2)
{% endhighlight %}

For simplicity, the above only takes the first 2 blocks into account. Expanding this to cover all (adjacent) blocks should be trivial.

#### References ####

[skullsecurity](https://blog.skullsecurity.org/2013/a-padding-oracle-example) and <NAME>'s [blog](http://robertheaton.com/2013/07/29/padding-oracle-attack/). This small article on [padbuster](http://blog.gdssecurity.com/labs/2010/9/14/automated-padding-oracle-attacks-with-padbuster.html) is neat too.

### 18. Implement CTR, the stream cipher mode ###

CTR mode isn't particularly complex, but we need to be careful about padding (or lack of). With CTR we essentially end up xor'ing a stream of data with our plaintext to generate ciphertext (or vice versa for decryption).

The following snippet illustrates how to do this as a standalone function. It's a little counter-intuitive but we don't use AES on the ciphertext itself - instead we use it on this incrementing counter function and only *then* do we xor it with the ciphertext.

{% highlight python %}
  def mc_part18():
    s = base64.b64decode(b'L77na/nrFsKvynd6HzOoG7GHTLXsTVu9qvY/2syLXzhPweyyMTJULu/6/kXX0KSvoOLSFQ==')
    counter = 0
    
    def fn():
      import struct
      nonlocal counter
      ret = struct.pack('<QQ', 0, counter) # 2x64b -> 128b, little-endian
      counter += 1
      return ret
  
    from Crypto.Cipher import AES
    cr = AES.new(b'YELLOW SUBMARINE', AES.MODE_ECB)
  
    r = bytearray()
    for i in range(len(s)//16+1):
      block = s[i*16:(i+1)*16] 
      r.extend( crypto_utils.xor_bytearrays(cr.encrypt(fn()), block) )
  
    print(bytes(r))
{% endhighlight %}

Which yields `b"Yo, VIP Let's kick it Ice, Ice, baby Ice, Ice, baby "`.

### 19. Break fixed-nonce CTR mode using substitions ###

### 20. Break fixed-nonce CTR statistically ###

### 21. Implement the MT19937 Mersenne Twister RNG ###

### 22. Crack an MT19937 seed ###

### 23. Clone an MT19937 RNG from its output ###

### 24. Create the MT19937 stream cipher and break it ###
{'fraction_non_alphanumeric': 0.1122750470051034, 'fraction_numerical': 0.04203599247918345, 'mean_word_length': 2.9973161567364466, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 10, 'https://': 2, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '336568', 'n_tokens_mistral': 2761, 'n_tokens_neox': 2513, 'n_words': 896}