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