[3] | 1 | """This file implements the chaffing algorithm. |
---|
| 2 | |
---|
| 3 | Winnowing and chaffing is a technique for enhancing privacy without requiring |
---|
| 4 | strong encryption. In short, the technique takes a set of authenticated |
---|
| 5 | message blocks (the wheat) and adds a number of chaff blocks which have |
---|
| 6 | randomly chosen data and MAC fields. This means that to an adversary, the |
---|
| 7 | chaff blocks look as valid as the wheat blocks, and so the authentication |
---|
| 8 | would have to be performed on every block. By tailoring the number of chaff |
---|
| 9 | blocks added to the message, the sender can make breaking the message |
---|
| 10 | computationally infeasible. There are many other interesting properties of |
---|
| 11 | the winnow/chaff technique. |
---|
| 12 | |
---|
| 13 | For example, say Alice is sending a message to Bob. She packetizes the |
---|
| 14 | message and performs an all-or-nothing transformation on the packets. Then |
---|
| 15 | she authenticates each packet with a message authentication code (MAC). The |
---|
| 16 | MAC is a hash of the data packet, and there is a secret key which she must |
---|
| 17 | share with Bob (key distribution is an exercise left to the reader). She then |
---|
| 18 | adds a serial number to each packet, and sends the packets to Bob. |
---|
| 19 | |
---|
| 20 | Bob receives the packets, and using the shared secret authentication key, |
---|
| 21 | authenticates the MACs for each packet. Those packets that have bad MACs are |
---|
| 22 | simply discarded. The remainder are sorted by serial number, and passed |
---|
| 23 | through the reverse all-or-nothing transform. The transform means that an |
---|
| 24 | eavesdropper (say Eve) must acquire all the packets before any of the data can |
---|
| 25 | be read. If even one packet is missing, the data is useless. |
---|
| 26 | |
---|
| 27 | There's one twist: by adding chaff packets, Alice and Bob can make Eve's job |
---|
| 28 | much harder, since Eve now has to break the shared secret key, or try every |
---|
| 29 | combination of wheat and chaff packet to read any of the message. The cool |
---|
| 30 | thing is that Bob doesn't need to add any additional code; the chaff packets |
---|
| 31 | are already filtered out because their MACs don't match (in all likelihood -- |
---|
| 32 | since the data and MACs for the chaff packets are randomly chosen it is |
---|
| 33 | possible, but very unlikely that a chaff MAC will match the chaff data). And |
---|
| 34 | Alice need not even be the party adding the chaff! She could be completely |
---|
| 35 | unaware that a third party, say Charles, is adding chaff packets to her |
---|
| 36 | messages as they are transmitted. |
---|
| 37 | |
---|
| 38 | For more information on winnowing and chaffing see this paper: |
---|
| 39 | |
---|
| 40 | Ronald L. Rivest, "Chaffing and Winnowing: Confidentiality without Encryption" |
---|
| 41 | http://theory.lcs.mit.edu/~rivest/chaffing.txt |
---|
| 42 | |
---|
| 43 | """ |
---|
| 44 | |
---|
| 45 | __revision__ = "$Id: Chaffing.py,v 1.7 2003/02/28 15:23:21 akuchling Exp $" |
---|
| 46 | |
---|
| 47 | from Crypto.Util.number import bytes_to_long |
---|
| 48 | |
---|
| 49 | class Chaff: |
---|
| 50 | """Class implementing the chaff adding algorithm. |
---|
| 51 | |
---|
| 52 | Methods for subclasses: |
---|
| 53 | |
---|
| 54 | _randnum(size): |
---|
| 55 | Returns a randomly generated number with a byte-length equal |
---|
| 56 | to size. Subclasses can use this to implement better random |
---|
| 57 | data and MAC generating algorithms. The default algorithm is |
---|
| 58 | probably not very cryptographically secure. It is most |
---|
| 59 | important that the chaff data does not contain any patterns |
---|
| 60 | that can be used to discern it from wheat data without running |
---|
| 61 | the MAC. |
---|
| 62 | |
---|
| 63 | """ |
---|
| 64 | |
---|
| 65 | def __init__(self, factor=1.0, blocksper=1): |
---|
| 66 | """Chaff(factor:float, blocksper:int) |
---|
| 67 | |
---|
| 68 | factor is the number of message blocks to add chaff to, |
---|
| 69 | expressed as a percentage between 0.0 and 1.0. blocksper is |
---|
| 70 | the number of chaff blocks to include for each block being |
---|
| 71 | chaffed. Thus the defaults add one chaff block to every |
---|
| 72 | message block. By changing the defaults, you can adjust how |
---|
| 73 | computationally difficult it could be for an adversary to |
---|
| 74 | brute-force crack the message. The difficulty is expressed |
---|
| 75 | as: |
---|
| 76 | |
---|
| 77 | pow(blocksper, int(factor * number-of-blocks)) |
---|
| 78 | |
---|
| 79 | For ease of implementation, when factor < 1.0, only the first |
---|
| 80 | int(factor*number-of-blocks) message blocks are chaffed. |
---|
| 81 | """ |
---|
| 82 | |
---|
| 83 | if not (0.0<=factor<=1.0): |
---|
| 84 | raise ValueError, "'factor' must be between 0.0 and 1.0" |
---|
| 85 | if blocksper < 0: |
---|
| 86 | raise ValueError, "'blocksper' must be zero or more" |
---|
| 87 | |
---|
| 88 | self.__factor = factor |
---|
| 89 | self.__blocksper = blocksper |
---|
| 90 | |
---|
| 91 | |
---|
| 92 | def chaff(self, blocks): |
---|
| 93 | """chaff( [(serial-number:int, data:string, MAC:string)] ) |
---|
| 94 | : [(int, string, string)] |
---|
| 95 | |
---|
| 96 | Add chaff to message blocks. blocks is a list of 3-tuples of the |
---|
| 97 | form (serial-number, data, MAC). |
---|
| 98 | |
---|
| 99 | Chaff is created by choosing a random number of the same |
---|
| 100 | byte-length as data, and another random number of the same |
---|
| 101 | byte-length as MAC. The message block's serial number is |
---|
| 102 | placed on the chaff block and all the packet's chaff blocks |
---|
| 103 | are randomly interspersed with the single wheat block. This |
---|
| 104 | method then returns a list of 3-tuples of the same form. |
---|
| 105 | Chaffed blocks will contain multiple instances of 3-tuples |
---|
| 106 | with the same serial number, but the only way to figure out |
---|
| 107 | which blocks are wheat and which are chaff is to perform the |
---|
| 108 | MAC hash and compare values. |
---|
| 109 | """ |
---|
| 110 | |
---|
| 111 | chaffedblocks = [] |
---|
| 112 | |
---|
| 113 | # count is the number of blocks to add chaff to. blocksper is the |
---|
| 114 | # number of chaff blocks to add per message block that is being |
---|
| 115 | # chaffed. |
---|
| 116 | count = len(blocks) * self.__factor |
---|
| 117 | blocksper = range(self.__blocksper) |
---|
| 118 | for i, wheat in map(None, range(len(blocks)), blocks): |
---|
| 119 | # it shouldn't matter which of the n blocks we add chaff to, so for |
---|
| 120 | # ease of implementation, we'll just add them to the first count |
---|
| 121 | # blocks |
---|
| 122 | if i < count: |
---|
| 123 | serial, data, mac = wheat |
---|
| 124 | datasize = len(data) |
---|
| 125 | macsize = len(mac) |
---|
| 126 | addwheat = 1 |
---|
| 127 | # add chaff to this block |
---|
| 128 | for j in blocksper: |
---|
| 129 | import sys |
---|
| 130 | chaffdata = self._randnum(datasize) |
---|
| 131 | chaffmac = self._randnum(macsize) |
---|
| 132 | chaff = (serial, chaffdata, chaffmac) |
---|
| 133 | # mix up the order, if the 5th bit is on then put the |
---|
| 134 | # wheat on the list |
---|
| 135 | if addwheat and bytes_to_long(self._randnum(16)) & 0x40: |
---|
| 136 | chaffedblocks.append(wheat) |
---|
| 137 | addwheat = 0 |
---|
| 138 | chaffedblocks.append(chaff) |
---|
| 139 | if addwheat: |
---|
| 140 | chaffedblocks.append(wheat) |
---|
| 141 | else: |
---|
| 142 | # just add the wheat |
---|
| 143 | chaffedblocks.append(wheat) |
---|
| 144 | return chaffedblocks |
---|
| 145 | |
---|
| 146 | def _randnum(self, size): |
---|
| 147 | # TBD: Not a very secure algorithm. |
---|
| 148 | # TBD: size * 2 to work around possible bug in RandomPool |
---|
| 149 | from Crypto.Util import randpool |
---|
| 150 | import time |
---|
| 151 | pool = randpool.RandomPool(size * 2) |
---|
| 152 | while size > pool.entropy: |
---|
| 153 | pass |
---|
| 154 | |
---|
| 155 | # we now have enough entropy in the pool to get size bytes of random |
---|
| 156 | # data... well, probably |
---|
| 157 | return pool.get_bytes(size) |
---|
| 158 | |
---|
| 159 | |
---|
| 160 | |
---|
| 161 | if __name__ == '__main__': |
---|
| 162 | text = """\ |
---|
| 163 | We hold these truths to be self-evident, that all men are created equal, that |
---|
| 164 | they are endowed by their Creator with certain unalienable Rights, that among |
---|
| 165 | these are Life, Liberty, and the pursuit of Happiness. That to secure these |
---|
| 166 | rights, Governments are instituted among Men, deriving their just powers from |
---|
| 167 | the consent of the governed. That whenever any Form of Government becomes |
---|
| 168 | destructive of these ends, it is the Right of the People to alter or to |
---|
| 169 | abolish it, and to institute new Government, laying its foundation on such |
---|
| 170 | principles and organizing its powers in such form, as to them shall seem most |
---|
| 171 | likely to effect their Safety and Happiness. |
---|
| 172 | """ |
---|
| 173 | print 'Original text:\n==========' |
---|
| 174 | print text |
---|
| 175 | print '==========' |
---|
| 176 | |
---|
| 177 | # first transform the text into packets |
---|
| 178 | blocks = [] ; size = 40 |
---|
| 179 | for i in range(0, len(text), size): |
---|
| 180 | blocks.append( text[i:i+size] ) |
---|
| 181 | |
---|
| 182 | # now get MACs for all the text blocks. The key is obvious... |
---|
| 183 | print 'Calculating MACs...' |
---|
| 184 | from Crypto.Hash import HMAC, SHA |
---|
| 185 | key = 'Jefferson' |
---|
| 186 | macs = [HMAC.new(key, block, digestmod=SHA).digest() |
---|
| 187 | for block in blocks] |
---|
| 188 | |
---|
| 189 | assert len(blocks) == len(macs) |
---|
| 190 | |
---|
| 191 | # put these into a form acceptable as input to the chaffing procedure |
---|
| 192 | source = [] |
---|
| 193 | m = map(None, range(len(blocks)), blocks, macs) |
---|
| 194 | print m |
---|
| 195 | for i, data, mac in m: |
---|
| 196 | source.append((i, data, mac)) |
---|
| 197 | |
---|
| 198 | # now chaff these |
---|
| 199 | print 'Adding chaff...' |
---|
| 200 | c = Chaff(factor=0.5, blocksper=2) |
---|
| 201 | chaffed = c.chaff(source) |
---|
| 202 | |
---|
| 203 | from base64 import encodestring |
---|
| 204 | |
---|
| 205 | # print the chaffed message blocks. meanwhile, separate the wheat from |
---|
| 206 | # the chaff |
---|
| 207 | |
---|
| 208 | wheat = [] |
---|
| 209 | print 'chaffed message blocks:' |
---|
| 210 | for i, data, mac in chaffed: |
---|
| 211 | # do the authentication |
---|
| 212 | h = HMAC.new(key, data, digestmod=SHA) |
---|
| 213 | pmac = h.digest() |
---|
| 214 | if pmac == mac: |
---|
| 215 | tag = '-->' |
---|
| 216 | wheat.append(data) |
---|
| 217 | else: |
---|
| 218 | tag = ' ' |
---|
| 219 | # base64 adds a trailing newline |
---|
| 220 | print tag, '%3d' % i, \ |
---|
| 221 | repr(data), encodestring(mac)[:-1] |
---|
| 222 | |
---|
| 223 | # now decode the message packets and check it against the original text |
---|
| 224 | print 'Undigesting wheat...' |
---|
| 225 | newtext = "".join(wheat) |
---|
| 226 | if newtext == text: |
---|
| 227 | print 'They match!' |
---|
| 228 | else: |
---|
| 229 | print 'They differ!' |
---|