[3] | 1 | """This file implements all-or-nothing package transformations. |
---|
| 2 | |
---|
| 3 | An all-or-nothing package transformation is one in which some text is |
---|
| 4 | transformed into message blocks, such that all blocks must be obtained before |
---|
| 5 | the reverse transformation can be applied. Thus, if any blocks are corrupted |
---|
| 6 | or lost, the original message cannot be reproduced. |
---|
| 7 | |
---|
| 8 | An all-or-nothing package transformation is not encryption, although a block |
---|
| 9 | cipher algorithm is used. The encryption key is randomly generated and is |
---|
| 10 | extractable from the message blocks. |
---|
| 11 | |
---|
| 12 | This class implements the All-Or-Nothing package transformation algorithm |
---|
| 13 | described in: |
---|
| 14 | |
---|
| 15 | Ronald L. Rivest. "All-Or-Nothing Encryption and The Package Transform" |
---|
| 16 | http://theory.lcs.mit.edu/~rivest/fusion.pdf |
---|
| 17 | |
---|
| 18 | """ |
---|
| 19 | |
---|
| 20 | __revision__ = "$Id: AllOrNothing.py,v 1.8 2003/02/28 15:23:20 akuchling Exp $" |
---|
| 21 | |
---|
| 22 | import operator |
---|
| 23 | import string |
---|
| 24 | from Crypto.Util.number import bytes_to_long, long_to_bytes |
---|
| 25 | |
---|
| 26 | |
---|
| 27 | |
---|
| 28 | class AllOrNothing: |
---|
| 29 | """Class implementing the All-or-Nothing package transform. |
---|
| 30 | |
---|
| 31 | Methods for subclassing: |
---|
| 32 | |
---|
| 33 | _inventkey(key_size): |
---|
| 34 | Returns a randomly generated key. Subclasses can use this to |
---|
| 35 | implement better random key generating algorithms. The default |
---|
| 36 | algorithm is probably not very cryptographically secure. |
---|
| 37 | |
---|
| 38 | """ |
---|
| 39 | |
---|
| 40 | def __init__(self, ciphermodule, mode=None, IV=None): |
---|
| 41 | """AllOrNothing(ciphermodule, mode=None, IV=None) |
---|
| 42 | |
---|
| 43 | ciphermodule is a module implementing the cipher algorithm to |
---|
| 44 | use. It must provide the PEP272 interface. |
---|
| 45 | |
---|
| 46 | Note that the encryption key is randomly generated |
---|
| 47 | automatically when needed. Optional arguments mode and IV are |
---|
| 48 | passed directly through to the ciphermodule.new() method; they |
---|
| 49 | are the feedback mode and initialization vector to use. All |
---|
| 50 | three arguments must be the same for the object used to create |
---|
| 51 | the digest, and to undigest'ify the message blocks. |
---|
| 52 | """ |
---|
| 53 | |
---|
| 54 | self.__ciphermodule = ciphermodule |
---|
| 55 | self.__mode = mode |
---|
| 56 | self.__IV = IV |
---|
| 57 | self.__key_size = ciphermodule.key_size |
---|
| 58 | if self.__key_size == 0: |
---|
| 59 | self.__key_size = 16 |
---|
| 60 | |
---|
| 61 | __K0digit = chr(0x69) |
---|
| 62 | |
---|
| 63 | def digest(self, text): |
---|
| 64 | """digest(text:string) : [string] |
---|
| 65 | |
---|
| 66 | Perform the All-or-Nothing package transform on the given |
---|
| 67 | string. Output is a list of message blocks describing the |
---|
| 68 | transformed text, where each block is a string of bit length equal |
---|
| 69 | to the ciphermodule's block_size. |
---|
| 70 | """ |
---|
| 71 | |
---|
| 72 | # generate a random session key and K0, the key used to encrypt the |
---|
| 73 | # hash blocks. Rivest calls this a fixed, publically-known encryption |
---|
| 74 | # key, but says nothing about the security implications of this key or |
---|
| 75 | # how to choose it. |
---|
| 76 | key = self._inventkey(self.__key_size) |
---|
| 77 | K0 = self.__K0digit * self.__key_size |
---|
| 78 | |
---|
| 79 | # we need two cipher objects here, one that is used to encrypt the |
---|
| 80 | # message blocks and one that is used to encrypt the hashes. The |
---|
| 81 | # former uses the randomly generated key, while the latter uses the |
---|
| 82 | # well-known key. |
---|
| 83 | mcipher = self.__newcipher(key) |
---|
| 84 | hcipher = self.__newcipher(K0) |
---|
| 85 | |
---|
| 86 | # Pad the text so that its length is a multiple of the cipher's |
---|
| 87 | # block_size. Pad with trailing spaces, which will be eliminated in |
---|
| 88 | # the undigest() step. |
---|
| 89 | block_size = self.__ciphermodule.block_size |
---|
| 90 | padbytes = block_size - (len(text) % block_size) |
---|
| 91 | text = text + ' ' * padbytes |
---|
| 92 | |
---|
| 93 | # Run through the algorithm: |
---|
| 94 | # s: number of message blocks (size of text / block_size) |
---|
| 95 | # input sequence: m1, m2, ... ms |
---|
| 96 | # random key K' (`key' in the code) |
---|
| 97 | # Compute output sequence: m'1, m'2, ... m's' for s' = s + 1 |
---|
| 98 | # Let m'i = mi ^ E(K', i) for i = 1, 2, 3, ..., s |
---|
| 99 | # Let m's' = K' ^ h1 ^ h2 ^ ... hs |
---|
| 100 | # where hi = E(K0, m'i ^ i) for i = 1, 2, ... s |
---|
| 101 | # |
---|
| 102 | # The one complication I add is that the last message block is hard |
---|
| 103 | # coded to the number of padbytes added, so that these can be stripped |
---|
| 104 | # during the undigest() step |
---|
| 105 | s = len(text) / block_size |
---|
| 106 | blocks = [] |
---|
| 107 | hashes = [] |
---|
| 108 | for i in range(1, s+1): |
---|
| 109 | start = (i-1) * block_size |
---|
| 110 | end = start + block_size |
---|
| 111 | mi = text[start:end] |
---|
| 112 | assert len(mi) == block_size |
---|
| 113 | cipherblock = mcipher.encrypt(long_to_bytes(i, block_size)) |
---|
| 114 | mticki = bytes_to_long(mi) ^ bytes_to_long(cipherblock) |
---|
| 115 | blocks.append(mticki) |
---|
| 116 | # calculate the hash block for this block |
---|
| 117 | hi = hcipher.encrypt(long_to_bytes(mticki ^ i, block_size)) |
---|
| 118 | hashes.append(bytes_to_long(hi)) |
---|
| 119 | |
---|
| 120 | # Add the padbytes length as a message block |
---|
| 121 | i = i + 1 |
---|
| 122 | cipherblock = mcipher.encrypt(long_to_bytes(i, block_size)) |
---|
| 123 | mticki = padbytes ^ bytes_to_long(cipherblock) |
---|
| 124 | blocks.append(mticki) |
---|
| 125 | |
---|
| 126 | # calculate this block's hash |
---|
| 127 | hi = hcipher.encrypt(long_to_bytes(mticki ^ i, block_size)) |
---|
| 128 | hashes.append(bytes_to_long(hi)) |
---|
| 129 | |
---|
| 130 | # Now calculate the last message block of the sequence 1..s'. This |
---|
| 131 | # will contain the random session key XOR'd with all the hash blocks, |
---|
| 132 | # so that for undigest(), once all the hash blocks are calculated, the |
---|
| 133 | # session key can be trivially extracted. Calculating all the hash |
---|
| 134 | # blocks requires that all the message blocks be received, thus the |
---|
| 135 | # All-or-Nothing algorithm succeeds. |
---|
| 136 | mtick_stick = bytes_to_long(key) ^ reduce(operator.xor, hashes) |
---|
| 137 | blocks.append(mtick_stick) |
---|
| 138 | |
---|
| 139 | # we convert the blocks to strings since in Python, byte sequences are |
---|
| 140 | # always represented as strings. This is more consistent with the |
---|
| 141 | # model that encryption and hash algorithms always operate on strings. |
---|
| 142 | return map(long_to_bytes, blocks) |
---|
| 143 | |
---|
| 144 | |
---|
| 145 | def undigest(self, blocks): |
---|
| 146 | """undigest(blocks : [string]) : string |
---|
| 147 | |
---|
| 148 | Perform the reverse package transformation on a list of message |
---|
| 149 | blocks. Note that the ciphermodule used for both transformations |
---|
| 150 | must be the same. blocks is a list of strings of bit length |
---|
| 151 | equal to the ciphermodule's block_size. |
---|
| 152 | """ |
---|
| 153 | |
---|
| 154 | # better have at least 2 blocks, for the padbytes package and the hash |
---|
| 155 | # block accumulator |
---|
| 156 | if len(blocks) < 2: |
---|
| 157 | raise ValueError, "List must be at least length 2." |
---|
| 158 | |
---|
| 159 | # blocks is a list of strings. We need to deal with them as long |
---|
| 160 | # integers |
---|
| 161 | blocks = map(bytes_to_long, blocks) |
---|
| 162 | |
---|
| 163 | # Calculate the well-known key, to which the hash blocks are |
---|
| 164 | # encrypted, and create the hash cipher. |
---|
| 165 | K0 = self.__K0digit * self.__key_size |
---|
| 166 | hcipher = self.__newcipher(K0) |
---|
| 167 | |
---|
| 168 | # Since we have all the blocks (or this method would have been called |
---|
| 169 | # prematurely), we can calcualte all the hash blocks. |
---|
| 170 | hashes = [] |
---|
| 171 | for i in range(1, len(blocks)): |
---|
| 172 | mticki = blocks[i-1] ^ i |
---|
| 173 | hi = hcipher.encrypt(long_to_bytes(mticki)) |
---|
| 174 | hashes.append(bytes_to_long(hi)) |
---|
| 175 | |
---|
| 176 | # now we can calculate K' (key). remember the last block contains |
---|
| 177 | # m's' which we don't include here |
---|
| 178 | key = blocks[-1] ^ reduce(operator.xor, hashes) |
---|
| 179 | |
---|
| 180 | # and now we can create the cipher object |
---|
| 181 | mcipher = self.__newcipher(long_to_bytes(key)) |
---|
| 182 | block_size = self.__ciphermodule.block_size |
---|
| 183 | |
---|
| 184 | # And we can now decode the original message blocks |
---|
| 185 | parts = [] |
---|
| 186 | for i in range(1, len(blocks)): |
---|
| 187 | cipherblock = mcipher.encrypt(long_to_bytes(i, block_size)) |
---|
| 188 | mi = blocks[i-1] ^ bytes_to_long(cipherblock) |
---|
| 189 | parts.append(mi) |
---|
| 190 | |
---|
| 191 | # The last message block contains the number of pad bytes appended to |
---|
| 192 | # the original text string, such that its length was an even multiple |
---|
| 193 | # of the cipher's block_size. This number should be small enough that |
---|
| 194 | # the conversion from long integer to integer should never overflow |
---|
| 195 | padbytes = int(parts[-1]) |
---|
| 196 | text = string.join(map(long_to_bytes, parts[:-1]), '') |
---|
| 197 | return text[:-padbytes] |
---|
| 198 | |
---|
| 199 | def _inventkey(self, key_size): |
---|
| 200 | # TBD: Not a very secure algorithm. Eventually, I'd like to use JHy's |
---|
| 201 | # kernelrand module |
---|
| 202 | import time |
---|
| 203 | from Crypto.Util import randpool |
---|
| 204 | # TBD: key_size * 2 to work around possible bug in RandomPool? |
---|
| 205 | pool = randpool.RandomPool(key_size * 2) |
---|
| 206 | while key_size > pool.entropy: |
---|
| 207 | pool.add_event() |
---|
| 208 | |
---|
| 209 | # we now have enough entropy in the pool to get a key_size'd key |
---|
| 210 | return pool.get_bytes(key_size) |
---|
| 211 | |
---|
| 212 | def __newcipher(self, key): |
---|
| 213 | if self.__mode is None and self.__IV is None: |
---|
| 214 | return self.__ciphermodule.new(key) |
---|
| 215 | elif self.__IV is None: |
---|
| 216 | return self.__ciphermodule.new(key, self.__mode) |
---|
| 217 | else: |
---|
| 218 | return self.__ciphermodule.new(key, self.__mode, self.__IV) |
---|
| 219 | |
---|
| 220 | |
---|
| 221 | |
---|
| 222 | if __name__ == '__main__': |
---|
| 223 | import sys |
---|
| 224 | import getopt |
---|
| 225 | import base64 |
---|
| 226 | |
---|
| 227 | usagemsg = '''\ |
---|
| 228 | Test module usage: %(program)s [-c cipher] [-l] [-h] |
---|
| 229 | |
---|
| 230 | Where: |
---|
| 231 | --cipher module |
---|
| 232 | -c module |
---|
| 233 | Cipher module to use. Default: %(ciphermodule)s |
---|
| 234 | |
---|
| 235 | --aslong |
---|
| 236 | -l |
---|
| 237 | Print the encoded message blocks as long integers instead of base64 |
---|
| 238 | encoded strings |
---|
| 239 | |
---|
| 240 | --help |
---|
| 241 | -h |
---|
| 242 | Print this help message |
---|
| 243 | ''' |
---|
| 244 | |
---|
| 245 | ciphermodule = 'AES' |
---|
| 246 | aslong = 0 |
---|
| 247 | |
---|
| 248 | def usage(code, msg=None): |
---|
| 249 | if msg: |
---|
| 250 | print msg |
---|
| 251 | print usagemsg % {'program': sys.argv[0], |
---|
| 252 | 'ciphermodule': ciphermodule} |
---|
| 253 | sys.exit(code) |
---|
| 254 | |
---|
| 255 | try: |
---|
| 256 | opts, args = getopt.getopt(sys.argv[1:], |
---|
| 257 | 'c:l', ['cipher=', 'aslong']) |
---|
| 258 | except getopt.error, msg: |
---|
| 259 | usage(1, msg) |
---|
| 260 | |
---|
| 261 | if args: |
---|
| 262 | usage(1, 'Too many arguments') |
---|
| 263 | |
---|
| 264 | for opt, arg in opts: |
---|
| 265 | if opt in ('-h', '--help'): |
---|
| 266 | usage(0) |
---|
| 267 | elif opt in ('-c', '--cipher'): |
---|
| 268 | ciphermodule = arg |
---|
| 269 | elif opt in ('-l', '--aslong'): |
---|
| 270 | aslong = 1 |
---|
| 271 | |
---|
| 272 | # ugly hack to force __import__ to give us the end-path module |
---|
| 273 | module = __import__('Crypto.Cipher.'+ciphermodule, None, None, ['new']) |
---|
| 274 | |
---|
| 275 | a = AllOrNothing(module) |
---|
| 276 | print 'Original text:\n==========' |
---|
| 277 | print __doc__ |
---|
| 278 | print '==========' |
---|
| 279 | msgblocks = a.digest(__doc__) |
---|
| 280 | print 'message blocks:' |
---|
| 281 | for i, blk in map(None, range(len(msgblocks)), msgblocks): |
---|
| 282 | # base64 adds a trailing newline |
---|
| 283 | print ' %3d' % i, |
---|
| 284 | if aslong: |
---|
| 285 | print bytes_to_long(blk) |
---|
| 286 | else: |
---|
| 287 | print base64.encodestring(blk)[:-1] |
---|
| 288 | # |
---|
| 289 | # get a new undigest-only object so there's no leakage |
---|
| 290 | b = AllOrNothing(module) |
---|
| 291 | text = b.undigest(msgblocks) |
---|
| 292 | if text == __doc__: |
---|
| 293 | print 'They match!' |
---|
| 294 | else: |
---|
| 295 | print 'They differ!' |
---|