Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-crypto

Source of release 0.6.0

0.6.0 / src / aes.lucb

## 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