1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
|
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<html><head><title>Python: module gdata.Crypto.Protocol.Chaffing</title>
</head><body bgcolor="#f0f0f8">
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="heading">
<tr bgcolor="#7799ee">
<td valign=bottom> <br>
<font color="#ffffff" face="helvetica, arial"> <br><big><big><strong><a href="gdata.html"><font color="#ffffff">gdata</font></a>.<a href="gdata.Crypto.html"><font color="#ffffff">Crypto</font></a>.<a href="gdata.Crypto.Protocol.html"><font color="#ffffff">Protocol</font></a>.Chaffing</strong></big></big></font></td
><td align=right valign=bottom
><font color="#ffffff" face="helvetica, arial"><a href=".">index</a><br><a href="file:/home/afshar/wrk/gdata-python-client/src/gdata/Crypto/Protocol/Chaffing.py">/home/afshar/wrk/gdata-python-client/src/gdata/Crypto/Protocol/Chaffing.py</a></font></td></tr></table>
<p><tt>This file implements the chaffing algorithm.<br>
<br>
Winnowing and chaffing is a technique for enhancing privacy without requiring<br>
strong encryption. In short, the technique takes a set of authenticated<br>
message blocks (the wheat) and adds a number of chaff blocks which have<br>
randomly chosen data and MAC fields. This means that to an adversary, the<br>
chaff blocks look as valid as the wheat blocks, and so the authentication<br>
would have to be performed on every block. By tailoring the number of chaff<br>
blocks added to the message, the sender can make breaking the message<br>
computationally infeasible. There are many other interesting properties of<br>
the winnow/chaff technique.<br>
<br>
For example, say Alice is sending a message to Bob. She packetizes the<br>
message and performs an all-or-nothing transformation on the packets. Then<br>
she authenticates each packet with a message authentication code (MAC). The<br>
MAC is a hash of the data packet, and there is a secret key which she must<br>
share with Bob (key distribution is an exercise left to the reader). She then<br>
adds a serial number to each packet, and sends the packets to Bob.<br>
<br>
Bob receives the packets, and using the shared secret authentication key,<br>
authenticates the MACs for each packet. Those packets that have bad MACs are<br>
simply discarded. The remainder are sorted by serial number, and passed<br>
through the reverse all-or-nothing transform. The transform means that an<br>
eavesdropper (say Eve) must acquire all the packets before any of the data can<br>
be read. If even one packet is missing, the data is useless.<br>
<br>
There's one twist: by adding chaff packets, Alice and Bob can make Eve's job<br>
much harder, since Eve now has to break the shared secret key, or try every<br>
combination of wheat and chaff packet to read any of the message. The cool<br>
thing is that Bob doesn't need to add any additional code; the chaff packets<br>
are already filtered out because their MACs don't match (in all likelihood --<br>
since the data and MACs for the chaff packets are randomly chosen it is<br>
possible, but very unlikely that a chaff MAC will match the chaff data). And<br>
Alice need not even be the party adding the chaff! She could be completely<br>
unaware that a third party, say Charles, is adding chaff packets to her<br>
messages as they are transmitted.<br>
<br>
For more information on winnowing and chaffing see this paper:<br>
<br>
Ronald L. Rivest, "Chaffing and Winnowing: Confidentiality without Encryption"<br>
<a href="http://theory.lcs.mit.edu/~rivest/chaffing.txt">http://theory.lcs.mit.edu/~rivest/chaffing.txt</a></tt></p>
<p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#ee77aa">
<td colspan=3 valign=bottom> <br>
<font color="#ffffff" face="helvetica, arial"><big><strong>Classes</strong></big></font></td></tr>
<tr><td bgcolor="#ee77aa"><tt> </tt></td><td> </td>
<td width="100%"><dl>
<dt><font face="helvetica, arial"><a href="gdata.Crypto.Protocol.Chaffing.html#Chaff">Chaff</a>
</font></dt></dl>
<p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#ffc8d8">
<td colspan=3 valign=bottom> <br>
<font color="#000000" face="helvetica, arial"><a name="Chaff">class <strong>Chaff</strong></a></font></td></tr>
<tr bgcolor="#ffc8d8"><td rowspan=2><tt> </tt></td>
<td colspan=2><tt>Class implementing the chaff adding algorithm.<br>
<br>
Methods for subclasses:<br>
<br>
_randnum(size):<br>
Returns a randomly generated number with a byte-length equal<br>
to size. Subclasses can use this to implement better random<br>
data and MAC generating algorithms. The default algorithm is<br>
probably not very cryptographically secure. It is most<br>
important that the chaff data does not contain any patterns<br>
that can be used to discern it from wheat data without running<br>
the MAC.<br> </tt></td></tr>
<tr><td> </td>
<td width="100%">Methods defined here:<br>
<dl><dt><a name="Chaff-__init__"><strong>__init__</strong></a>(self, factor<font color="#909090">=1.0</font>, blocksper<font color="#909090">=1</font>)</dt><dd><tt><a href="#Chaff">Chaff</a>(factor:float, blocksper:int)<br>
<br>
factor is the number of message blocks to add chaff to,<br>
expressed as a percentage between 0.0 and 1.0. blocksper is<br>
the number of chaff blocks to include for each block being<br>
chaffed. Thus the defaults add one chaff block to every<br>
message block. By changing the defaults, you can adjust how<br>
computationally difficult it could be for an adversary to<br>
brute-force crack the message. The difficulty is expressed<br>
as:<br>
<br>
pow(blocksper, int(factor * number-of-blocks))<br>
<br>
For ease of implementation, when factor < 1.0, only the first<br>
int(factor*number-of-blocks) message blocks are chaffed.</tt></dd></dl>
<dl><dt><a name="Chaff-chaff"><strong>chaff</strong></a>(self, blocks)</dt><dd><tt><a href="#Chaff-chaff">chaff</a>( [(serial-number:int, data:string, MAC:string)] )<br>
: [(int, string, string)]<br>
<br>
Add chaff to message blocks. blocks is a list of 3-tuples of the<br>
form (serial-number, data, MAC).<br>
<br>
<a href="#Chaff">Chaff</a> is created by choosing a random number of the same<br>
byte-length as data, and another random number of the same<br>
byte-length as MAC. The message block's serial number is<br>
placed on the chaff block and all the packet's chaff blocks<br>
are randomly interspersed with the single wheat block. This<br>
method then returns a list of 3-tuples of the same form.<br>
Chaffed blocks will contain multiple instances of 3-tuples<br>
with the same serial number, but the only way to figure out<br>
which blocks are wheat and which are chaff is to perform the<br>
MAC hash and compare values.</tt></dd></dl>
</td></tr></table></td></tr></table><p>
<table width="100%" cellspacing=0 cellpadding=2 border=0 summary="section">
<tr bgcolor="#55aa55">
<td colspan=3 valign=bottom> <br>
<font color="#ffffff" face="helvetica, arial"><big><strong>Data</strong></big></font></td></tr>
<tr><td bgcolor="#55aa55"><tt> </tt></td><td> </td>
<td width="100%"><strong>__revision__</strong> = '$Id: Chaffing.py,v 1.7 2003/02/28 15:23:21 akuchling Exp $'</td></tr></table>
</body></html>
|
