4 ### Generalization of OCB mode for other block sizes
6 ### (c) 2017 Mark Wooding
9 ###----- Licensing notice ---------------------------------------------------
11 ### This program is free software; you can redistribute it and/or modify
12 ### it under the terms of the GNU General Public License as published by
13 ### the Free Software Foundation; either version 2 of the License, or
14 ### (at your option) any later version.
16 ### This program is distributed in the hope that it will be useful,
17 ### but WITHOUT ANY WARRANTY; without even the implied warranty of
18 ### MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 ### GNU General Public License for more details.
21 ### You should have received a copy of the GNU General Public License
22 ### along with this program; if not, write to the Free Software Foundation,
23 ### Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
25 from sys import argv, stderr
26 from struct import pack
27 from itertools import izip
28 from contextlib import contextmanager
29 try: from kalyna import Kalyna
30 except ImportError: Kalyna = None
35 ###--------------------------------------------------------------------------
42 yield [things[i] for i in ii]
44 if j == k - 1: lim = n
57 try: return POLYMAP[nbits]
59 base = C.GF(0).setbit(nbits).setbit(0)
60 for k in xrange(1, nbits, 2):
61 for cc in combs(range(1, nbits), k):
62 p = base + sum(C.GF(0).setbit(c) for c in cc)
63 if p.irreduciblep(): POLYMAP[nbits] = p; return p
64 raise ValueError, nbits
67 ## No fancy way to do this: I'd need a much cleverer factoring algorithm
68 ## than I have in my pockets.
69 if nbits == 64: cc = [64, 4, 3, 1, 0]
70 elif nbits == 96: cc = [96, 10, 9, 6, 0]
71 elif nbits == 128: cc = [128, 7, 2, 1, 0]
72 elif nbits == 192: cc = [192, 15, 11, 5, 0]
73 elif nbits == 256: cc = [256, 10, 5, 2, 0]
74 else: raise ValueError, 'no field for %d bits' % nbits
76 for c in cc: p = p.setbit(c)
80 return C.ByteString.zero(n)
82 def mul_blk_gf(m, x, p): return ((C.GF.loadb(m)*x)%p).storeb((p.nbits + 6)/8)
87 except StopIteration: raise ValueError, 'empty iter'
92 except StopIteration: lastp = True
96 if len(x): return hex(x)
101 if isinstance(ksz, C.KeySZSet): kk = ksz.set
102 elif isinstance(ksz, C.KeySZRange): kk = range(ksz.min, ksz.max, ksz.mod)
103 elif isinstance(ksz, C.KeySZAny): kk = range(64); sel = [0]
104 kk = list(kk); kk = kk[:]
106 while n and len(sel) < 4:
109 kk[i], kk[n] = kk[n], kk[i]
116 else: r = (-len(m))%w
118 return C.ByteString(m)
122 if r: m += '\x80' + Z(r - 1)
123 return C.ByteString(m)
127 while (i&1) == 0: i >>= 1; j += 1
131 v, i, n = [], 0, len(x)
133 v.append(C.ByteString(x[i:i + w]))
135 return v, C.ByteString(x[i:])
141 if len(tl) == w: v.append(tl); tl = EMPTY
144 ###--------------------------------------------------------------------------
145 ### Kalyna decoration.
149 if Kalyna is not None:
151 class KalynaCipher (type):
152 def __new__(cls, blksz):
153 assert blksz in [16, 32, 64]
154 name = 'Kalyna-%d' % (8*blksz)
155 me = type(name, (KalynaBase,), {})
158 if blksz == 64: me.keysz = C.KeySZSet(64)
159 else: me.keysz = C.KeySZSet(2*blksz, [blksz])
162 class KalynaBase (object):
164 me._k = Kalyna(k, me.blksz)
166 return C.ByteString(me._k.encrypt(m))
168 return C.ByteString(me._k.decrypt(m))
170 for i in [16, 32, 64]:
171 KALYNA['kalyna%d' % (8*i)] = KalynaCipher(i)
173 ###--------------------------------------------------------------------------
174 ### Luby--Rackoff large-block ciphers.
176 class LubyRackoffCipher (type):
177 def __new__(cls, bc, blksz):
179 assert blksz <= 2*bc.blksz
180 name = '%s-lr[%d]' % (bc.name, 8*blksz)
181 me = type(name, (LubyRackoffBase,), {})
190 global VERBOSE, LRVERBOSE
191 _v, _lrv = VERBOSE, LRVERBOSE
193 VERBOSE = LRVERBOSE = False
196 VERBOSE, LRVERBOSE = _v, _lrv
198 class LubyRackoffBase (object):
199 NR = 4 # for strong-PRP security
201 if LRVERBOSE: print 'K = %s' % hex(k)
202 bc, blksz = me.__class__.bc, me.__class__.blksz
203 with muffle(): E = bc(k)
207 for j in xrange(me.NR):
210 with muffle(): x = E.encrypt(i.storeb(bc.blksz))
212 if LRVERBOSE: print 'E(K; [%d]) = %s' % (i, hex(x))
214 kj = C.ByteString(C.ByteString(b)[0:ksz])
215 if LRVERBOSE: print 'K_%d = %s' % (j, hex(kj))
216 with muffle(): me.f.append(bc(kj))
218 bc, blksz = me.__class__.bc, me.__class__.blksz
219 assert len(m) == blksz
220 l, r = C.ByteString(m[:blksz/2]), C.ByteString(m[blksz/2:])
221 if LRVERBOSE: print 'L_0, R_0 = %s, %s' % (hex(l), hex(r))
222 for j in xrange(me.NR):
223 l0 = pad0star(l, bc.blksz)
224 with muffle(): t = me.f[j].encrypt(l0)
225 l, r = r ^ t[:blksz/2], l
227 print 'E(K_%d; L_%d || 0^*) = %s' % (j, j, hex(t))
228 print 'L_%d, R_%d = %s, %s' % (j + 1, j + 1, hex(l), hex(r))
229 return C.ByteString(r + l)
231 bc, blksz = me.__class__.bc, me.__class__.blksz
232 assert len(c) == blksz
233 l, r = C.ByteString(c[:blksz/2]), C.ByteString(c[blksz/2:])
234 for j in xrange(me.NR - 1, -1, -1):
235 l0 = pad0star(l, bc.blksz)
236 with muffle(): t = me.f[j].encrypt(l0)
238 print 'L_%d, R_%d = %s, %s' % (j + 1, j + 1, hex(l), hex(r))
239 print 'E(K_%d; L_%d || 0^*) = %s' % (j + 1, j + 1, hex(t))
240 l, r = r ^ t[:blksz/2], l
241 if LRVERBOSE: print 'L_0, R_0 = %s, %s' % (hex(l), hex(r))
242 return C.ByteString(r + l)
245 for i in [8, 12, 16, 24, 32]:
246 LRAES['lraes%d' % (8*i)] = LubyRackoffCipher(C.rijndael, i)
247 LRAES['dlraes512'] = LubyRackoffCipher(LubyRackoffCipher(C.rijndael, 32), 64)
249 ###--------------------------------------------------------------------------
253 blksz = E.__class__.blksz
255 x = C.GF(2); xinv = p.modinv(x)
258 Lxinv = mul_blk_gf(L, xinv, p)
260 for i in xrange(1, len(Lgamma)):
261 Lgamma[i] = mul_blk_gf(Lgamma[i - 1], x, p)
265 Lgamma, Lxinv = ocb_masks(E)
266 print 'L x^-1 = %s' % hex(Lxinv)
267 for i, lg in enumerate(Lgamma):
268 print 'L x^%d = %s' % (i, hex(lg))
271 blksz = E.__class__.blksz
272 Lgamma, Lxinv = ocb_masks(E)
275 v, tl = blocks(m, blksz)
279 a ^= E.encrypt(x ^ o)
281 print 'Z[%d]: %d -> %s' % (i - 1, b, hex(o))
282 print 'A[%d]: %s' % (i - 1, hex(a))
284 if len(tl) == blksz: a ^= tl ^ Lxinv
285 else: a ^= pad10star(tl, blksz)
289 blksz = E.__class__.blksz
291 L = E.encrypt(Z(blksz))
292 o = mul_blk_gf(L, 10, p)
294 v, tl = blocks(m, blksz)
296 a ^= E.encrypt(x ^ o)
297 o = mul_blk_gf(o, 2, p)
298 if len(tl) == blksz: a ^= tl ^ mul_blk_gf(o, 3, p)
299 else: a ^= pad10star(tl, blksz) ^ mul_blk_gf(o, 5, p)
303 Lgamma, _ = ocb_masks(E)
306 return Lstar, Ldollar, Lgamma[2:]
309 Lstar, Ldollar, Lgamma = ocb3_masks(E)
310 print 'L_* : %s' % hex(Lstar)
311 print 'L_$ : %s' % hex(Ldollar)
312 for i, lg in enumerate(Lgamma[:4]):
313 print 'L_%-8d: %s' % (i, hex(lg))
316 blksz = E.__class__.blksz
317 Lstar, Ldollar, Lgamma = ocb3_masks(E)
320 v, tl = blocks0(m, blksz)
324 a ^= E.encrypt(x ^ o)
326 print 'Offset\'_%-2d: %s' % (i, hex(o))
327 print 'AuthSum_%-2d: %s' % (i, hex(a))
331 a ^= E.encrypt(pad10star(tl, blksz) ^ o)
333 print 'Offset\'_* : %s' % hex(o)
334 print 'AuthSum_* : %s' % hex(a)
338 if VERBOSE: dump_ocb(E)
352 ###--------------------------------------------------------------------------
355 ## For OCB2, it's important for security that n = log_x (x + 1) is large in
356 ## the field representations of GF(2^w) used -- in fact, we need more, that
357 ## i n (mod 2^w - 1) is large for i in {4, -3, -2, -1, 1, 2, 3, 4}. The
358 ## original paper lists the values for 64 and 128, but we support other block
359 ## sizes, so here's the result of the (rather large, in some cases)
362 ## Block size log_x (x + 1)
364 ## 64 9686038906114705801
365 ## 96 63214690573408919568138788065
366 ## 128 338793687469689340204974836150077311399
367 ## 192 161110085006042185925119981866940491651092686475226538785
368 ## 256 22928580326165511958494515843249267194111962539778797914076675796261938307298
370 def ocb1(E, n, h, m, tsz = None):
371 ## This is OCB1.PMAC1 from Rogaway's `Authenticated-Encryption with
373 blksz = E.__class__.blksz
374 if VERBOSE: dump_ocb(E)
375 Lgamma, Lxinv = ocb_masks(E)
376 if tsz is None: tsz = blksz
378 o = E.encrypt(n ^ Lgamma[0])
379 if VERBOSE: print 'R = %s' % hex(o)
382 v, tl = blocks(m, blksz)
388 print 'Z[%d]: %d -> %s' % (i - 1, b, hex(o))
389 print 'A[%d]: %s' % (i - 1, hex(a))
390 y.put(E.encrypt(x ^ o) ^ o)
396 print 'Z[%d]: %d -> %s' % (i - 1, b, hex(o))
397 print 'LEN = %s' % hex(C.MP(8*n).storeb(blksz))
398 yfinal = E.encrypt(C.MP(8*n).storeb(blksz) ^ Lxinv ^ o)
399 cfinal = tl ^ yfinal[:n]
400 a ^= o ^ (tl + yfinal[n:])
403 if h: t ^= pmac1(E, h)
404 return C.ByteString(y), C.ByteString(t[:tsz])
406 def ocb2(E, n, h, m, tsz = None):
407 blksz = E.__class__.blksz
408 if tsz is None: tsz = blksz
411 o = mul_blk_gf(L, 2, p)
413 v, tl = blocks(m, blksz)
417 y.put(E.encrypt(x ^ o) ^ o)
418 o = mul_blk_gf(o, 2, p)
420 yfinal = E.encrypt(C.MP(8*n).storeb(blksz) ^ o)
421 cfinal = tl ^ yfinal[:n]
422 a ^= (tl + yfinal[n:]) ^ mul_blk_gf(o, 3, p)
425 if h: t ^= pmac2(E, h)
426 return C.ByteString(y), C.ByteString(t[:tsz])
428 OCB3_STRETCH = { 8: (5, 25),
435 def ocb3(E, n, h, m, tsz = None):
436 blksz = E.__class__.blksz
437 if tsz is None: tsz = blksz
438 Lstar, Ldollar, Lgamma = ocb3_masks(E)
439 if VERBOSE: dump_ocb3(E)
441 ## Figure out how much we need to glue onto the nonce. This ends up being
442 ## [t mod w]_v || 0^p || 1 || N, where w is the block size in bits, t is
443 ## the tag length in bits, v = floor(log_2(w - 1)) + 1, and p = w - l(N) -
444 ## v - 1. But this is an annoying way to think about it because of the
445 ## byte misalignment. Instead, think of it as a byte-aligned prefix
446 ## encoding the tag and an `is the nonce full-length' flag, followed by
447 ## optional padding, and then the nonce:
449 ## F || N if l(N) = w - f
450 ## F || 0^p || 1 || N otherwise
452 ## where F is [t mod w]_v || 0^{f-v-1} || b; f = floor(log_2(w - 1)) + 2;
453 ## b is 1 if l(N) = w - f, or 0 otherwise; and p = w - f - l(N) - 1.
454 tszbits = C.MP(8*blksz - 1).nbits
456 f = tsz << 3 + 8*fwd - tszbits
458 ## Form the augmented nonce.
460 nsz, nwd = len(n), blksz - fwd
461 if nsz == nwd: f |= 1
462 nb.put(C.MP(f).storeb(fwd))
463 if nsz < nwd: nb.zero(nwd - nsz - 1).putu8(1)
465 nn = C.ByteString(nb)
466 if VERBOSE: print 'N\' : %s' % hex(nn)
468 ## Calculate the initial offset.
469 split, shift = OCB3_STRETCH[blksz]
470 splitbits = 1 << split
471 t2ps = C.MP(0).setbit(splitbits)
472 lomask = (C.MP(0).setbit(split) - 1)
474 top, bottom = nn&himask.storeb2c(blksz), C.MP.loadb(nn)&lomask
475 ktop = C.MP.loadb(E.encrypt(top))
476 stretch = (ktop << splitbits) | \
477 (((ktop ^ (ktop << shift)) >> (8*blksz - splitbits))%t2ps)
478 o = (stretch >> splitbits - bottom).storeb(blksz)
479 a = C.ByteString.zero(blksz)
481 print 'bottom : %d' % bottom
482 print 'Ktop : %s' % hex(ktop.storeb(blksz))
483 print 'Stretch : %s' % hex(stretch.storeb(blksz + (1 << split - 3)))
484 print 'Offset_0 : %s' % hex(o)
486 ## Split the message into blocks.
489 v, tl = blocks0(m, blksz)
495 print 'Offset_%-3d: %s' % (i, hex(o))
496 print 'Checksum_%d: %s' % (i, hex(a))
497 y.put(E.encrypt(x ^ o) ^ o)
503 a ^= pad10star(tl, blksz)
505 print 'Offset_* : %s' % hex(o)
506 print 'Checksum_*: %s' % hex(a)
509 t = E.encrypt(a ^ o) ^ pmac3(E, h)
510 return C.ByteString(y), C.ByteString(t[:tsz])
514 return [(w, 0, 0), (w, 1, 0), (w, 0, 1),
518 (w, 3*w - 5, 3*w + 5)]
522 return [(w - 2, 0, 0), (w - 2, 1, 0), (w - 2, 0, 1),
526 (w - 2, 3*w - 5, 3*w + 5)]
528 ###--------------------------------------------------------------------------
531 VERBOSE = LRVERBOSE = False
533 class struct (object):
534 def __init__(me, **kw):
535 me.__dict__.update(kw)
537 def mct(ocb, bc, ksz, nsz, tsz):
538 k = C.MP(8*tsz).storeb(ksz)
542 cbuf = C.WriteBuffer()
543 for i in xrange(128):
544 s = C.ByteString.zero(i)
545 y, t = ocb(E, n.storeb(nsz), s, s, tsz); n += 1; cbuf.put(y).put(t)
546 y, t = ocb(E, n.storeb(nsz), e, s, tsz); n += 1; cbuf.put(y).put(t)
547 y, t = ocb(E, n.storeb(nsz), s, e, tsz); n += 1; cbuf.put(y).put(t)
548 _, t = ocb(E, n.storeb(nsz), C.ByteString(cbuf), e, tsz)
556 usage: %s [-v] OCB BLKC OP ARGS...
558 kat K N0 TSZ HSZ,MSZ ...
559 lraes W K M""" % argv[0]
562 def arg(must = True, default = None):
564 if argi < argc: argi += 1; return argv[argi - 1]
565 elif not must: return default
568 MODEMAP = { 'ocb1': ocb1,
574 for i in xrange(sz): b.putu8(i%256)
575 return C.ByteString(b)
578 if opt == '-v': VERBOSE = True; opt = arg()
583 for d in LRAES, KALYNA, C.gcprps:
585 except KeyError: pass
587 if bc is None: raise KeyError, bcname
591 ksz = int(arg()); nsz = int(arg()); tsz = int(arg())
592 mct(ocb, bc, ksz, nsz, tsz)
599 if nspec.endswith('+'): ninc = 1; nspec = nspec[:-1]
606 print 'K: %s' % hex(k)
609 hmsz = arg(must = False)
610 if hmsz is None: break
611 hsz, msz = map(int, hmsz.split(','))
615 y, t = ocb(E, n, h, m, tsz)
617 print 'N: %s' % hex(n)
618 print 'A: %s' % hex(h)
619 print 'P: %s' % hex(m)
620 print 'C: %s%s' % (hex(y), hex(t))
623 elif mode == 'lraes':
628 lr = LubyRackoffCipher(bc, w)
632 print 'E\'(K, m) = %s' % hex(c)
637 ###----- That's all, folks --------------------------------------------------