Posted By

weilawei on 07/20/12


Tagged

stream Encryption Cryptography cipher RC4 ARC4 RC4A RC4-drop8192 VMPC IARC4


Versions (?)

Improved ARC4 (IARC4)


 / Published in: Python
 

This code is public domain.

Improved ARC4 (IARC4) contains a number of proposed improvements over naive ARC4:

  • Uses KSA from VMPC minus an IV.
  • Uses 2 state spaces (RC4A). Splits the key and nonce to produce a key and nonce for each state space. Each subkey and subnonce is XOR'd together to produce a new subkey. TODO: They should be hashed, but they are not currently, until I select a hash function with an appropriately sized output, which won't limit the keyspace available to IARC4.
  • Takes a nonce alongside the key. The key and nonce must be random and of even, equal length, with 512 bytes per key/nonce suggested.
  • Drops the first 8192 (4096 per state space) iterations of the PRNG (RC4-drop8192).
  • A KeyExpiredError is raised after 255 iterations of the PRNG, excluding the initial drop. Passing the expires option to IARC4 will alter this limit.

This code should not be considered secure. It has not been cryptanalyzed and should not be used in production. This code is strictly experimental.

  1. #!/usr/bin/env python3
  2.  
  3. # This code is public domain.
  4. #
  5. # Improved ARC4 (IARC4) contains a number of proposed improvements over naive ARC4:
  6. #
  7. # - Uses KSA from VMPC minus an IV.
  8. # - Uses 2 state spaces (RC4A). Splits the key and nonce to produce a key and nonce for each
  9. # state space. Each subkey and subnonce is XOR'd together to produce a new subkey.
  10. # - Takes a nonce alongside the key. The key and nonce must be random and of even, equal
  11. # length, with 512 bytes per key/nonce suggested. **TODO**: They should be hashed, but they
  12. # are not currently, until I select a hash function with an appropriately sized output, which
  13. # won't limit the keyspace available to IARC4.
  14. # - Drops the first 8192 (4096 per state space) iterations of the PRNG (RC4-drop8192).
  15. # - A KeyExpiredError is raised after 255 iterations of the PRNG, excluding the initial drop.
  16. # Passing the `expires` option to IARC4 will alter this limit.
  17. #
  18. # This code should not be considered secure. It has not been cryptanalyzed and should not be used
  19. # in production. This code is strictly experimental.
  20.  
  21. from bitstring import BitArray
  22. from Crypto.Random import random
  23.  
  24. # Generates a random n-byte string. Makes no checks to ensure uniqueness.
  25. def random_bytes(n_bytes=512):
  26. return BitArray(uint=random.getrandbits(n_bytes*8), length=(n_bytes*8)).bytes
  27.  
  28. # VMPC state preparation without vector
  29. def prepare_state(key, state_size=256):
  30. key_size = len(key)
  31. state = [i for i in range(state_size)]
  32. j = 0
  33.  
  34. for n in range(state_size*3):
  35. i = n % state_size
  36. j = state[(((j + state[i]) % state_size) + key[i % key_size]) % state_size]
  37.  
  38. state[i] ^= state[j]
  39. state[j] ^= state[i]
  40. state[i] ^= state[j]
  41.  
  42. return state
  43.  
  44. # Generic error (e.g., key and nonce of different lengths)
  45. class KeyError(Exception): pass
  46.  
  47. # Raised if a key/nonce combination has been used too many times already (255).
  48. class KeyExpiredError(KeyError): pass
  49.  
  50. # Uses 2 state spaces (RC4A)
  51. def pseudorandom_generator(state_a, state_b, state_size=256, expires=8447):
  52. i = 0
  53. j_a = 0
  54. j_b = 0
  55. n = 0
  56.  
  57. while True:
  58. n += 1
  59.  
  60. i = (i + 1) % state_size
  61. j_a = (j_a + state_a[i]) % state_size
  62.  
  63. state_a[i] ^= state_a[j_a]
  64. state_a[j_a] ^= state_a[i]
  65. state_a[i] ^= state_a[j_a]
  66.  
  67. yield state_b[(state_a[i] + state_a[j_a]) % state_size]
  68.  
  69. # Limit the PRNG to 255 iterations after dropping 8192 iterations
  70. if (n == expires): break
  71. n += 1
  72.  
  73. j_b = (j_b + state_b[i]) % state_size
  74.  
  75. state_b[i] ^= state_b[j_b]
  76. state_b[j_b] ^= state_b[i]
  77. state_b[i] ^= state_b[j_b]
  78.  
  79. yield state_a[(state_b[i] + state_b[j_b]) % state_size]
  80.  
  81. raise KeyExpiredError
  82.  
  83. # Main keystream generation and ciphering.
  84. def IARC4(key, nonce, drop=8192, expires=255):
  85. key_length = len(key)
  86.  
  87. # Keys and nonces must be of even, equal lengths, 512 bytes apiece is recommended.
  88. if ((key_length != len(nonce)) or ((key_length % 2) != 0)):
  89. raise KeyError
  90.  
  91. # Split key and nonce in half to gain key_a, key_b, nonce_a, and nonce_b
  92. key_split = key_length >> 1
  93. key_a = BitArray(bytes=key[:key_split])
  94. key_b = BitArray(bytes=key[key_split:])
  95. nonce_a = BitArray(bytes=nonce[:key_split])
  96. nonce_b = BitArray(bytes=nonce[key_split:])
  97.  
  98. # XOR keys and nonces.
  99. key_a = (key_a ^ nonce_a).bytes
  100. key_b = (key_b ^ nonce_b).bytes
  101.  
  102. # Prepare the PRNG
  103. state_a = prepare_state(key_a)
  104. state_b = prepare_state(key_b)
  105. keystream = pseudorandom_generator(state_a, state_b, expires=(drop + expires))
  106.  
  107. # Discard first 4096 iterations of each state space
  108. for dropped in range(drop): next(keystream)
  109.  
  110. # Return the prepared PRNG to begin accepting input
  111. def _IARC4(text):
  112. # Combine the keystream and the text stream
  113. for key_byte, text_byte in zip(keystream, text):
  114. yield key_byte ^ text_byte
  115.  
  116. return _IARC4
  117.  
  118. # Test Vector for IARC4
  119. #
  120. # nonce: b'\x01' + bytes(255) + b'\x02' + bytes(255)
  121. # key: b'key_a' + bytes(251) + b'key_b' + bytes(251)
  122. # plaintext: b'Plaintext'
  123. # ciphertext: b'\xb1\xc5\x8d)\x90\xf9WN\x94'
  124.  
  125. if (__name__ == "__main__"):
  126. nonce = b'\x01' + bytes(255) + b'\x02' + bytes(255)
  127. key = b'key_a' + bytes(251) + b'key_b' + bytes(251)
  128. plaintext = b'Plaintext'
  129. stream_length = len(plaintext)
  130. encrypter = IARC4(key, nonce)
  131. encryption = encrypter(plaintext)
  132. ciphertext = bytes([next(encryption) for i in range(stream_length)])
  133. decrypter = IARC4(key, nonce)
  134. decryption = decrypter(ciphertext)
  135. plaintext = bytes([next(decryption) for i in range(stream_length)])
  136.  
  137. print("nonce: %s\nkey: %s\nplaintext: %s\nciphertext: %s" %
  138. (nonce, key, plaintext, ciphertext))

Report this snippet  

You need to login to post a comment.