dymokomi/luce-crypto
Source of release 0.6.1
## FIPS 197 AES-128/192/256 encryption in constant-time bitsliced form, four
## blocks at a time in eight 64-bit words, plus the 32-bit-counter CTR mode
## that GCM uses. There are no secret-indexed table lookups or secret-dependent
## branches: the S-box is the Boyar–Peralta circuit (eprint 2009/191). The
## structure follows Thomas Pornin's BearSSL `aes_ct64` (MIT); see NOTICE.md.
## Only encryption is provided, which is all CTR and GCM need.
import secure
import sha2
import memory
## Expanded round keys in bitsliced form: eight words per round key.
pub struct Key:
var rounds: usize
var words: u64[120]
## Erase the round keys of this exact object.
pub func wipe():
secure.wipe(u8[]((u8*)&self, memory.size_of(Key)))
## The S-box applied to all 32 bytes held across the eight bit-planes `q`.
## q[7] holds the high bit (x0 in the paper's numbering), q[0] the low bit.
func sbox(q: u64[]):
let x0 = q[7]
let x1 = q[6]
let x2 = q[5]
let x3 = q[4]
let x4 = q[3]
let x5 = q[2]
let x6 = q[1]
let x7 = q[0]
# Top linear transformation.
let y14 = x3 ^ x5
let y13 = x0 ^ x6
let y9 = x0 ^ x3
let y8 = x0 ^ x5
let t0 = x1 ^ x2
let y1 = t0 ^ x7
let y4 = y1 ^ x3
let y12 = y13 ^ y14
let y2 = y1 ^ x0
let y5 = y1 ^ x6
let y3 = y5 ^ y8
let t1 = x4 ^ y12
let y15 = t1 ^ x5
let y20 = t1 ^ x1
let y6 = y15 ^ x7
let y10 = y15 ^ t0
let y11 = y20 ^ y9
let y7 = x7 ^ y11
let y17 = y10 ^ y11
let y19 = y10 ^ y8
let y16 = t0 ^ y11
let y21 = y13 ^ y16
let y18 = x0 ^ y16
# Non-linear section.
let t2 = y12 & y15
let t3 = y3 & y6
let t4 = t3 ^ t2
let t5 = y4 & x7
let t6 = t5 ^ t2
let t7 = y13 & y16
let t8 = y5 & y1
let t9 = t8 ^ t7
let t10 = y2 & y7
let t11 = t10 ^ t7
let t12 = y9 & y11
let t13 = y14 & y17
let t14 = t13 ^ t12
let t15 = y8 & y10
let t16 = t15 ^ t12
let t17 = t4 ^ t14
let t18 = t6 ^ t16
let t19 = t9 ^ t14
let t20 = t11 ^ t16
let t21 = t17 ^ y20
let t22 = t18 ^ y19
let t23 = t19 ^ y21
let t24 = t20 ^ y18
let t25 = t21 ^ t22
let t26 = t21 & t23
let t27 = t24 ^ t26
let t28 = t25 & t27
let t29 = t28 ^ t22
let t30 = t23 ^ t24
let t31 = t22 ^ t26
let t32 = t31 & t30
let t33 = t32 ^ t24
let t34 = t23 ^ t33
let t35 = t27 ^ t33
let t36 = t24 & t35
let t37 = t36 ^ t34
let t38 = t27 ^ t36
let t39 = t29 & t38
let t40 = t25 ^ t39
let t41 = t40 ^ t37
let t42 = t29 ^ t33
let t43 = t29 ^ t40
let t44 = t33 ^ t37
let t45 = t42 ^ t41
let z0 = t44 & y15
let z1 = t37 & y6
let z2 = t33 & x7
let z3 = t43 & y16
let z4 = t40 & y1
let z5 = t29 & y7
let z6 = t42 & y11
let z7 = t45 & y17
let z8 = t41 & y10
let z9 = t44 & y12
let z10 = t37 & y3
let z11 = t33 & y4
let z12 = t43 & y13
let z13 = t40 & y5
let z14 = t29 & y2
let z15 = t42 & y9
let z16 = t45 & y14
let z17 = t41 & y8
# Bottom linear transformation.
let t46 = z15 ^ z16
let t47 = z10 ^ z11
let t48 = z5 ^ z13
let t49 = z9 ^ z10
let t50 = z2 ^ z12
let t51 = z2 ^ z5
let t52 = z7 ^ z8
let t53 = z0 ^ z3
let t54 = z6 ^ z7
let t55 = z16 ^ z17
let t56 = z12 ^ t48
let t57 = t50 ^ t53
let t58 = z4 ^ t46
let t59 = z3 ^ t54
let t60 = t46 ^ t57
let t61 = z14 ^ t57
let t62 = t52 ^ t58
let t63 = t49 ^ t58
let t64 = z4 ^ t59
let t65 = t61 ^ t62
let t66 = z1 ^ t63
let s0 = t59 ^ t63
let s6 = t56 ^ ~t62
let s7 = t48 ^ ~t60
let t67 = t64 ^ t65
let s3 = t53 ^ t66
let s4 = t51 ^ t66
let s5 = t47 ^ t65
let s1 = t64 ^ ~s3
let s2 = t55 ^ ~t67
q[7] = s0
q[6] = s1
q[5] = s2
q[4] = s3
q[3] = s4
q[2] = s5
q[1] = s6
q[0] = s7
func swap_bits(q: u64[], a: usize, b: usize, low: u64, high: u64, shift: u64):
let x = q[a]
let y = q[b]
q[a] = (x & low) | ((y & low) << shift)
q[b] = ((x & high) >> shift) | (y & high)
## Transpose between byte order and bit planes; it is its own inverse.
func ortho(q: u64[]):
swap_bits(q, 0, 1, 0x5555555555555555, 0xaaaaaaaaaaaaaaaa, 1)
swap_bits(q, 2, 3, 0x5555555555555555, 0xaaaaaaaaaaaaaaaa, 1)
swap_bits(q, 4, 5, 0x5555555555555555, 0xaaaaaaaaaaaaaaaa, 1)
swap_bits(q, 6, 7, 0x5555555555555555, 0xaaaaaaaaaaaaaaaa, 1)
swap_bits(q, 0, 2, 0x3333333333333333, 0xcccccccccccccccc, 2)
swap_bits(q, 1, 3, 0x3333333333333333, 0xcccccccccccccccc, 2)
swap_bits(q, 4, 6, 0x3333333333333333, 0xcccccccccccccccc, 2)
swap_bits(q, 5, 7, 0x3333333333333333, 0xcccccccccccccccc, 2)
swap_bits(q, 0, 4, 0x0f0f0f0f0f0f0f0f, 0xf0f0f0f0f0f0f0f0, 4)
swap_bits(q, 1, 5, 0x0f0f0f0f0f0f0f0f, 0xf0f0f0f0f0f0f0f0, 4)
swap_bits(q, 2, 6, 0x0f0f0f0f0f0f0f0f, 0xf0f0f0f0f0f0f0f0, 4)
swap_bits(q, 3, 7, 0x0f0f0f0f0f0f0f0f, 0xf0f0f0f0f0f0f0f0, 4)
func spread(x: u64) -> u64:
var v = (x | (x << 16)) & 0x0000ffff0000ffff
v = (v | (v << 8)) & 0x00ff00ff00ff00ff
return v
func gather(x: u64) -> u64:
var v = x & 0x00ff00ff00ff00ff
v = (v | (v >> 8)) & 0x0000ffff0000ffff
return v | (v >> 16)
## Spread one block's four little-endian words over two state words.
func interleave_in(q: u64[], first: usize, second: usize, w: const u32[]):
let x0 = spread((u64)w[0])
let x1 = spread((u64)w[1])
let x2 = spread((u64)w[2])
let x3 = spread((u64)w[3])
q[first] = x0 | (x2 << 8)
q[second] = x1 | (x3 << 8)
func interleave_out(w: u32[], q0: u64, q1: u64):
w[0] = (u32)(gather(q0) & 0xffffffff)
w[1] = (u32)(gather(q1) & 0xffffffff)
w[2] = (u32)(gather(q0 >> 8) & 0xffffffff)
w[3] = (u32)(gather(q1 >> 8) & 0xffffffff)
func load32(bytes: const u8[], at: usize) -> u32:
return (u32)bytes[at] | ((u32)bytes[at + 1] << 8) | ((u32)bytes[at + 2] << 16) | ((u32)bytes[at + 3] << 24)
func store32(bytes: u8[], at: usize, value: u32):
bytes[at] = (u8)(value & 0xff)
bytes[at + 1] = (u8)((value >> 8) & 0xff)
bytes[at + 2] = (u8)((value >> 16) & 0xff)
bytes[at + 3] = (u8)(value >> 24)
func sub_word(x: u32) -> u32:
var q: u64[8]
q[0] = (u64)x
ortho(q)
sbox(q)
ortho(q)
return (u32)(q[0] & 0xffffffff)
## Expand a 16-, 24- or 32-byte key (FIPS 197 §5.2) into bitsliced round keys.
pub func expand(key: const u8[]) -> Key!:
if key.length != 16 and key.length != 24 and key.length != 32:
error(sha2.invalid, "AES key must be 16, 24 or 32 bytes")
let rcon: u8[10] = [0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1b, 0x36]
let nk = key.length // 4
var out = Key(rounds = nk + 6)
let total = (out.rounds + 1) * 4
var schedule: u32[60]
defer secure.wipe(u8[]((u8*)&schedule[0], memory.size_of(schedule)))
for i in 0..<nk:
schedule[i] = load32(key, i * 4)
var previous = schedule[nk - 1]
var j: usize = 0
var k: usize = 0
for i in nk..<total:
if j == 0:
previous = (previous << 24) | (previous >> 8)
previous = sub_word(previous) ^ (u32)rcon[k]
elif nk > 6 and j == 4:
previous = sub_word(previous)
previous ^= schedule[i - nk]
schedule[i] = previous
j += 1
if j == nk:
j = 0
k += 1
var q: u64[8]
defer secure.wipe(u8[]((u8*)&q[0], memory.size_of(q)))
var i: usize = 0
while i < total:
interleave_in(q, 0, 4, schedule[i..<i + 4])
q[1] = q[0]
q[2] = q[0]
q[3] = q[0]
q[5] = q[4]
q[6] = q[4]
q[7] = q[4]
ortho(q)
let compressed0 = (q[0] & 0x1111111111111111) | (q[1] & 0x2222222222222222) | (q[2] & 0x4444444444444444) | (q[3] & 0x8888888888888888)
let compressed1 = (q[4] & 0x1111111111111111) | (q[5] & 0x2222222222222222) | (q[6] & 0x4444444444444444) | (q[7] & 0x8888888888888888)
let at = i * 2
decompress(out.words[at..<at + 4], compressed0)
decompress(out.words[at + 4..<at + 8], compressed1)
i += 4
return out
## Broadcast each of the four interleaved key planes in a compressed word.
func decompress(out: u64[], compressed: u64):
let x0 = compressed & 0x1111111111111111
let x1 = (compressed & 0x2222222222222222) >> 1
let x2 = (compressed & 0x4444444444444444) >> 2
let x3 = (compressed & 0x8888888888888888) >> 3
out[0] = (x0 << 4) -% x0
out[1] = (x1 << 4) -% x1
out[2] = (x2 << 4) -% x2
out[3] = (x3 << 4) -% x3
func add_round_key(q: u64[], key: const u64[]):
for i in 0..<(usize)8:
q[i] ^= key[i]
func shift_rows(q: u64[]):
for i in 0..<(usize)8:
let x = q[i]
q[i] = (x & 0x000000000000ffff) | ((x & 0x00000000fff00000) >> 4) | ((x & 0x00000000000f0000) << 12) | ((x & 0x0000ff0000000000) >> 8) | ((x & 0x000000ff00000000) << 8) | ((x & 0xf000000000000000) >> 12) | ((x & 0x0fff000000000000) << 4)
func rotate16(x: u64) -> u64:
return (x >> 16) | (x << 48)
func rotate32(x: u64) -> u64:
return (x << 32) | (x >> 32)
func mix_columns(q: u64[]):
let q0 = q[0]
let q1 = q[1]
let q2 = q[2]
let q3 = q[3]
let q4 = q[4]
let q5 = q[5]
let q6 = q[6]
let q7 = q[7]
let r0 = rotate16(q0)
let r1 = rotate16(q1)
let r2 = rotate16(q2)
let r3 = rotate16(q3)
let r4 = rotate16(q4)
let r5 = rotate16(q5)
let r6 = rotate16(q6)
let r7 = rotate16(q7)
q[0] = q7 ^ r7 ^ r0 ^ rotate32(q0 ^ r0)
q[1] = q0 ^ r0 ^ q7 ^ r7 ^ r1 ^ rotate32(q1 ^ r1)
q[2] = q1 ^ r1 ^ r2 ^ rotate32(q2 ^ r2)
q[3] = q2 ^ r2 ^ q7 ^ r7 ^ r3 ^ rotate32(q3 ^ r3)
q[4] = q3 ^ r3 ^ q7 ^ r7 ^ r4 ^ rotate32(q4 ^ r4)
q[5] = q4 ^ r4 ^ r5 ^ rotate32(q5 ^ r5)
q[6] = q5 ^ r5 ^ r6 ^ rotate32(q6 ^ r6)
q[7] = q6 ^ r6 ^ r7 ^ rotate32(q7 ^ r7)
## Encrypt the four blocks held in bitsliced state `q`.
func encrypt_state(key: const Key*, q: u64[]):
add_round_key(q, key.words[..<8])
for round in 1..<key.rounds:
sbox(q)
shift_rows(q)
mix_columns(q)
add_round_key(q, key.words[round * 8..<round * 8 + 8])
sbox(q)
shift_rows(q)
add_round_key(q, key.words[key.rounds * 8..<key.rounds * 8 + 8])
## Encrypt up to four 16-byte blocks in `blocks` (64 bytes) in place.
func encrypt4(key: const Key*, blocks: u8[]):
var w: u32[16]
var q: u64[8]
defer secure.wipe(u8[]((u8*)&w[0], memory.size_of(w)))
defer secure.wipe(u8[]((u8*)&q[0], memory.size_of(q)))
for i in 0..<(usize)16:
w[i] = load32(blocks, i * 4)
for i in 0..<(usize)4:
interleave_in(q, i, i + 4, w[i * 4..<i * 4 + 4])
ortho(q)
encrypt_state(key, q)
ortho(q)
for i in 0..<(usize)4:
interleave_out(w[i * 4..<i * 4 + 4], q[i], q[i + 4])
for i in 0..<(usize)16:
store32(blocks, i * 4, w[i])
## Encrypt one 16-byte block.
pub func encrypt_block(key: const Key*, input: const u8[], output: u8[]) -> !:
if input.length != 16 or output.length < 16:
error(sha2.invalid, "AES block input must be 16 bytes")
var blocks: u8[64]
defer secure.wipe(blocks)
for i in 0..<(usize)16:
blocks[i] = input[i]
encrypt4(key, blocks)
for i in 0..<(usize)16:
output[i] = blocks[i]
## CTR mode with a 96-bit nonce and a 32-bit big-endian block counter starting
## at `counter` (NIST SP 800-38D GCTR). `output` may alias `input` exactly.
## Returns the counter after the last block used.
pub func ctr32(key: const Key*, nonce: const u8[], counter: u32, input: const u8[], output: u8[]) -> u32!:
if nonce.length != 12:
error(sha2.invalid, "AES-CTR nonce must be 12 bytes")
if output.length < input.length:
error(sha2.invalid, "AES-CTR output is shorter than input")
var stream: u8[64]
defer secure.wipe(stream)
var next = counter
var at: usize = 0
while at < input.length:
for b in 0..<(usize)4:
for i in 0..<(usize)12:
stream[b * 16 + i] = nonce[i]
let value = next +% (u32)b
stream[b * 16 + 12] = (u8)(value >> 24)
stream[b * 16 + 13] = (u8)((value >> 16) & 0xff)
stream[b * 16 + 14] = (u8)((value >> 8) & 0xff)
stream[b * 16 + 15] = (u8)(value & 0xff)
encrypt4(key, stream)
let take = 64 if input.length - at > 64 else input.length - at
for i in 0..<take:
output[at + i] = input[at + i] ^ stream[i]
next +%= (u32)((take + 15) // 16)
at += take
return next