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