[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[minion-cvs] Improved comments on performance.
Update of /home/minion/cvsroot/src/minion/lib/mixminion
In directory moria.seul.org:/tmp/cvs-serv8424/lib/mixminion
Modified Files:
BuildMessage.py Crypto.py ServerProcess.py benchmark.py
test.py
Log Message:
Improved comments on performance.
Remove a (futile) optimization from _minionlib.sha1.
Add a (measurably productive) optimization: remember expanded AES keys.
New LIONESS key schedule.
Implement replay prevention.
Fix use of interfaces in ServerProcess.
New tests and benchmarks for the above.
Index: BuildMessage.py
===================================================================
RCS file: /home/minion/cvsroot/src/minion/lib/mixminion/BuildMessage.py,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- BuildMessage.py 29 May 2002 03:52:13 -0000 1.1
+++ BuildMessage.py 29 May 2002 17:46:23 -0000 1.2
@@ -110,7 +110,7 @@
for i in range(hops-1, -1, -1):
jnk = junk[i]
rest = Crypto.strxor(header, masks[i])
- digest = Crypto.sha1(rest + junk[i])
+ digest = Crypto.sha1(rest+junk[i])
pubkey = Crypto.pk_from_modulus(nodes[i].getModulus())
rt, ri = routing[i]
subhead = Subheader(MAJOR_NO, MINOR_NO,
Index: Crypto.py
===================================================================
RCS file: /home/minion/cvsroot/src/minion/lib/mixminion/Crypto.py,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- Crypto.py 29 May 2002 03:52:13 -0000 1.1
+++ Crypto.py 29 May 2002 17:46:23 -0000 1.2
@@ -2,7 +2,11 @@
# $Id$
"""mixminion.Crypto
- This package contains XXXX"""
+ This package contains all the cryptographic primitives required
+ my the Mixminion spec. Some of these are wrappers for functionality
+ implemented in C by OpenSSL. Nonetheless, other modules should call
+ the functions in mixminion.Crypto, and not call _minionlib's crypto
+ functionality themselves."""
import sys
import mixminion._minionlib as _ml
@@ -34,19 +38,29 @@
def sha1(s):
"""sha1(s) -> str
- Returns the SHA1 hash of a string"""
+ Returns the SHA1 hash of its argument"""
return _ml.sha1(s)
+def strxor(s1, s2):
+ """strxor(s1, s2) -> str
+
+ Computes the bitwise xor of two strings. Raises an exception if the
+ strings' lengths are unequal."""
+ return _ml.strxor(s1, s2)
+
def ctr_crypt(s, key, idx=0):
"""ctr_crypt(s, key, idx=0) -> str
Given a string s and a 16-byte key key, computes the AES counter-mode
encryption of s using k. The counter begins at idx."""
-
+ if type(key) == str:
+ key = _ml.aes_key(key)
return _ml.aes_ctr128_crypt(key,s,idx)
def prng(key,count,idx=0):
"""Returns the bytestream 0x00000000...., encrypted in counter mode."""
+ if type(key) == str:
+ key = _ml.aes_key(key)
return _ml.aes_ctr128_crypt(key,"",idx,count)
def lioness_encrypt(s,key):
@@ -64,11 +78,15 @@
left = s[:20]
right = s[20:]
del s
+ # Performance note: This business with sha1("".join([key,right,key]))
+ # may look slow, but it contributes only a 6% to the hashing step,
+ # which in turn contributes under 11% of the time for LIONESS.
+
#XXXX This slice makes me nervous
right = ctr_crypt(right, _ml.strxor(left,key1)[:16])
- left = _ml.strxor(left, _ml.sha1(right, key2))
- right = ctr_crypt(right, _ml.strxor(left, key3)[:16])
- left = _ml.strxor(left, _ml.sha1(right, key4))
+ left = _ml.strxor(left, _ml.sha1("".join([key2,right,key2])))
+ right = ctr_crypt(right, _ml.strxor(left,key3)[:16])
+ left = _ml.strxor(left, _ml.sha1("".join([key4,right,key4])))
return left + right
def lioness_decrypt(s,key):
@@ -87,9 +105,9 @@
right = s[20:]
del s
#XXXX This slice makes me nervous
- left = _ml.strxor(left, _ml.sha1(right, key4))
+ left = _ml.strxor(left, _ml.sha1("".join([key4,right,key4])))
right = ctr_crypt(right, _ml.strxor(left, key3)[:16])
- left = _ml.strxor(left, _ml.sha1(right, key2))
+ left = _ml.strxor(left, _ml.sha1("".join([key2,right,key2])))
right = ctr_crypt(right, _ml.strxor(left, key1)[:16])
return left + right
@@ -170,6 +188,7 @@
HEADER_ENCRYPT_MODE = "HEADER ENCRYPT"
PAYLOAD_ENCRYPT_MODE = "PAYLOAD ENCRYPT"
HIDE_HEADER_MODE = "HIDE HEADER"
+REPLAY_PREVENTION_MODE = "REPLAY PREVENTION"
class Keyset:
"""A Keyset represents a set of keys generated from a single master
@@ -191,10 +210,12 @@
Returns a set of 4 lioness keys, as described in the Mixminion
specification."""
- return (self.get(mode+" (FIRST SUBKEY)", 20),
- self.get(mode+" (SECOND SUBKEY)", 16),
- self.get(mode+" (THIRD SUBKEY)", 20),
- self.get(mode+" (FOURTH SUBKEY)", 16))
+ key1 = sha1(self.master+mode)
+ key3 = key1[:-1]+_ml.strxor(key1[-1],"\x02")
+ key2 = key1[:AES_KEY_LEN-1] + _ml.strxor(key1[AES_KEY_LEN-1], "\x01")
+ key4 = key1[:AES_KEY_LEN-1] + _ml.strxor(key1[AES_KEY_LEN-1], "\x03")
+
+ return (key1, key2, key3, key4)
def lioness_keys_from_payload(payload):
# XXXX Temporary method till George and I agree on a key schedule.
@@ -210,7 +231,7 @@
self.counter = 0
self.bytes = ""
if seed==None: seed=trng(AESCounterPRNG._KEYSIZE)
- self.key = seed
+ self.key = _ml.aes_key(seed)
def getBytes(self, n):
if n > len(self.bytes):
Index: ServerProcess.py
===================================================================
RCS file: /home/minion/cvsroot/src/minion/lib/mixminion/ServerProcess.py,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- ServerProcess.py 29 May 2002 03:52:13 -0000 1.1
+++ ServerProcess.py 29 May 2002 17:46:23 -0000 1.2
@@ -27,7 +27,7 @@
# Returns oneof (None), (method, argl)
def _processMessage(self, msg):
msg = Formats.parseMessage(msg)
- header1 = msg.header1
+ header1 = Formats.parseHeader(msg.header1)
subh = header1[0]
subh = Crypto.pk_decrypt(subh, self.privatekey)
subh = Formats.parseSubheader(subh)
@@ -35,7 +35,7 @@
if subh.major != 3 or subh.minor != 0:
raise ContentError("Invalid protocol version")
- digest = Crypto.sha1(header1[1:16])
+ digest = Crypto.sha1(header1[1:])
if digest != subh.digest:
raise ContentError("Invalid digest")
@@ -50,13 +50,19 @@
else:
remainingHeader = header1[1:]
+ # Replay prevention
keys = Crypto.Keyset(subh.master)
-
+ replayhash = keys.get(Crypto.REPLAY_PREVENTION_MODE, 20)
+ if self.hashlog.seenHash(replayhash):
+ raise ContentError("Duplicate message detected.")
+ else:
+ self.hashlog.logHash(replayhash)
+
if type == Modules.DROP_TYPE:
return None
- payload = Crypto.sprp_decrypt(msg.payload,
- keys.get(Crypto.PAYLOAD_ENCRYPT_MODE))
+ payload = Crypto.lioness_decrypt(msg.payload,
+ keys.get(Crypto.PAYLOAD_ENCRYPT_MODE))
# XXXX This doesn't match what George said.
if type > Modules.MIN_EXIT_TYPE:
@@ -74,12 +80,12 @@
header1 = Crypto.ctr_crypt(remainingHeader,
keys.get(Crypto.HEADER_SECRET_MODE))
- header2 = Crypto.sprp_decrypt(msg.header2,
- keys.get(Crypto.HEADER_ENCRYPT_MODE))
+ header2 = Crypto.lioness_decrypt(msg.header2,
+ keys.get(Crypto.HEADER_ENCRYPT_MODE))
if type == Modules.SWAP_FWD_TYPE:
- header2 = Crypto.sprp_decrypt(msg.header2,
- keys.get(Crypto.HIDE_HEADER_MODE))
+ hkey = Crypto.get_lioness_keys_from_payload(payload)
+ header2 = Crypto.lioness_decrypt(msg.header2, hkey)
header1, header2 = header2, header1
address = Formats.parseIPV4Info(subh.routinginfo)
Index: benchmark.py
===================================================================
RCS file: /home/minion/cvsroot/src/minion/lib/mixminion/benchmark.py,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- benchmark.py 29 May 2002 03:52:13 -0000 1.1
+++ benchmark.py 29 May 2002 17:46:23 -0000 1.2
@@ -67,10 +67,12 @@
print "SHA1 (32K)", timeit((lambda : sha1(s32K)), 1000)
shakey = "8charstr"*2
- print "Keyed SHA1 (short)",
- print timeit((lambda : _ml.sha1(short,shakey)), 100000)
- print "Keyed SHA1 (8K)", timeit((lambda : _ml.sha1(s8K, shakey)), 10000)
- print "Keyed SHA1 (32K)", timeit((lambda : _ml.sha1(s32K, shakey)), 1000)
+ #print "Keyed SHA1 (short)",
+ #print timeit((lambda : _ml.sha1(short,shakey)), 100000)
+ #print "Keyed SHA1 (8K)", timeit((lambda : _ml.sha1(s8K, shakey)), 10000)
+ #print "Keyed SHA1 (32K)", timeit((lambda : _ml.sha1(s32K, shakey)), 1000)
+ print "Lioness-keyed SHA1 (32K, unoptimized)", timeit(
+ (lambda : _ml.sha1("".join([shakey,s32K,shakey]))), 1000)
print "TRNG (20 byte)", timeit((lambda: trng(20)), 100)
print "TRNG (128 byte)", timeit((lambda: trng(128)), 100)
@@ -84,9 +86,19 @@
print "aes (1K)", timeit((lambda: ctr_crypt(s1K,key)), 10000)
print "aes (32K)", timeit((lambda: ctr_crypt(s32K,key)), 100)
+ key = _ml.aes_key(key)
+ print "aes (short,pre-key)", timeit((lambda: ctr_crypt(short,key)), 100000)
+ print "aes (1K,pre-key)", timeit((lambda: ctr_crypt(s1K,key)), 10000)
+ print "aes (32K,pre-key)", timeit((lambda: ctr_crypt(s32K,key)), 100)
+
+ print "aes (32K,pre-key,unoptimized)", timeit(
+ (lambda: _ml.strxor(prng(key,32768),s32K)), 100)
+
print "prng (short)", timeit((lambda: prng(key,8)), 100000)
print "prng (1K)", timeit((lambda: prng(key,1024)), 10000)
- print "prng (32)", timeit((lambda: prng(key,32768)), 100)
+ print "prng (32K)", timeit((lambda: prng(key,32768)), 100)
+ print "prng (32K, unoptimized)", timeit(
+ (lambda: ctr_crypt('\x00'*32768, key)), 100)
lkey = Keyset("keymaterial foo bar baz").getLionessKeys("T")
print "lioness E (1K)", timeit((lambda: lioness_encrypt(s1K, lkey)), 1000)
@@ -160,11 +172,11 @@
def testLeaks1():
print "Trying to leak (sha1,aes,xor,seed,oaep)"
s20k="a"*20*1024
- key="a"*16
+ keytxt="a"*16
+ key = _ml.aes_key(keytxt)
while 1:
if 1:
_ml.sha1(s20k)
- _ml.sha1(s20k,s20k)
_ml.aes_ctr128_crypt(key,s20k,0)
_ml.aes_ctr128_crypt(key,s20k,2000)
_ml.aes_ctr128_crypt(key,"",2000,20000)
@@ -176,7 +188,7 @@
pass
_ml.strxor(s20k,s20k)
try:
- _ml.strxor(s20k,key)
+ _ml.strxor(s20k,keytxt)
except:
pass
_ml.openssl_seed(s20k)
Index: test.py
===================================================================
RCS file: /home/minion/cvsroot/src/minion/lib/mixminion/test.py,v
retrieving revision 1.1
retrieving revision 1.2
diff -u -d -r1.1 -r1.2
--- test.py 29 May 2002 03:52:13 -0000 1.1
+++ test.py 29 May 2002 17:46:23 -0000 1.2
@@ -28,34 +28,43 @@
self.assertEquals(s,
self.hexread("84983E441C3BD26EBAAE4AA1F95129E5E54670F1"))
- self.assertEquals(s1("abc", "def"),
- s1("defabcdef"))
self.failUnlessRaises(TypeError, s1, 1)
def test_xor(self):
xor = _ml.strxor
+
self.assertEquals(xor("abc", "\000\000\000"), "abc")
self.assertEquals(xor("abc", "abc"), "\000\000\000")
self.assertEquals(xor("\xEF\xF0\x12", "\x11\x22\x35"), '\xFE\xD2\x27')
+ # Make sure that the C doesn't (cringe) modify the strings.
+ a = "aaaa"
+ self.assertEquals(xor(a,"\000\000\000a"), "aaa\000")
+ self.assertEquals(a, "aaaa")
+ self.assertEquals(xor("\000\000\000a",a), "aaa\000")
+ self.assertEquals(a, "aaaa")
+
self.failUnlessRaises(TypeError, xor, "a", "bb")
def test_aes(self):
crypt = _ml.aes_ctr128_crypt
# One of the test vectors from AES.
- key = "\x80" + "\x00" * 15
+ key = txt = "\x80" + "\x00" * 15
+ key = _ml.aes_key(key)
+
expected = self.hexread("8EDD33D3C621E546455BD8BA1418BEC8")
- self.failUnless(crypt(key, key, 0) == expected)
- self.failUnless(crypt(key, key) == expected)
+ self.failUnless(crypt(key, txt, 0) == expected)
+ self.failUnless(crypt(key, txt) == expected)
self.failUnless(crypt(key, " "*100, 0)[1:] == crypt(key, " "*99, 1))
self.failUnless(crypt(key,crypt(key, " "*100, 0),0) == " "*100)
teststr = """I have seen the best ciphers of my generation
Destroyed by cryptanalysis, broken, insecure,
Implemented still in cryptographic libraries"""
-
- self.assertEquals(teststr,crypt("xyzz"*4,crypt("xyzz"*4,teststr)))
+
+ key2 = _ml.aes_key("xyzz"*4)
+ self.assertEquals(teststr,crypt(key2,crypt(key2,teststr)))
# PRNG mode
expected2 = self.hexread("0EDD33D3C621E546455BD8BA1418BEC8")
@@ -143,7 +152,7 @@
def test_wrappers(self):
self.assertEquals(_ml.sha1("xyzzy"), sha1("xyzzy"))
- k = "xyzy"*4
+ k = _ml.aes_key("xyzy"*4)
self.assertEquals(_ml.aes_ctr128_crypt(k,"hello",0),
ctr_crypt("hello",k))
self.assertEquals(_ml.aes_ctr128_crypt(k,"hello",99),
@@ -198,12 +207,15 @@
def test_keyset(self):
s = sha1
+ x = _ml.strxor
k = Keyset("a")
eq = self.assertEquals
eq(s("aFoo")[:10], k.get("Foo",10))
eq(s("aBar")[:16], k.get("Bar"))
- eq( (s("aBaz (FIRST SUBKEY)"), s("aBaz (SECOND SUBKEY)")[:16],
- s("aBaz (THIRD SUBKEY)"), s("aBaz (FOURTH SUBKEY)")[:16]),
+ z15 = "\x00"*15
+ z19 = "\x00"*19
+ eq( (s("aBaz"), x(s("aBaz")[:16], z15+"\x01"),
+ x(s("aBaz"),z19+"\x02"), x(s("aBaz")[:16], z15+"\x03") ),
k.getLionessKeys("Baz"))
def test_aesprng(self):