1// PMAC message authentication code, defined in
2// http://web.cs.ucdavis.edu/~rogaway/ocb/pmac.pdf
3
4package pmac
5
6import (
7	"crypto/cipher"
8	"crypto/subtle"
9	"hash"
10	"math/bits"
11
12	"github.com/miscreant/miscreant.go/block"
13)
14
15// Number of L blocks to precompute (i.e. µ in the PMAC paper)
16// TODO: dynamically compute these as needed
17const precomputedBlocks = 31
18
19type pmac struct {
20	// c is the block cipher we're using (i.e. AES-128 or AES-256)
21	c cipher.Block
22
23	// l is defined as follows (quoted from the PMAC paper):
24	//
25	// Equation 1:
26	//
27	//     a · x =
28	//         a<<1 if firstbit(a)=0
29	//         (a<<1) ⊕ 0¹²⁰10000111 if firstbit(a)=1
30	//
31	// Equation 2:
32	//
33	//     a · x⁻¹ =
34	//         a>>1 if lastbit(a)=0
35	//         (a>>1) ⊕ 10¹²⁰1000011 if lastbit(a)=1
36	//
37	// Let L(0) ← L. For i ∈ [1..µ], compute L(i) ← L(i − 1) · x by
38	// Equation (1) using a shift and a conditional xor.
39	//
40	// Compute L(−1) ← L · x⁻¹ by Equation (2), using a shift and a
41	// conditional xor.
42	//
43	// Save the values L(−1), L(0), L(1), L(2), ..., L(µ) in a table.
44	// (Alternatively, [ed: as we have done in this codebase] defer computing
45	// some or  all of these L(i) values until the value is actually needed.)
46	l [precomputedBlocks]block.Block
47
48	// lInv contains the multiplicative inverse (i.e. right shift) of the first
49	// l-value, computed as described above, and is XORed into the tag in the
50	// event the message length is a multiple of the block size
51	lInv block.Block
52
53	// digest contains the PMAC tag-in-progress
54	digest block.Block
55
56	// offset is a block specific tweak to the input message
57	offset block.Block
58
59	// buf contains a part of the input message, processed a block-at-a-time
60	buf block.Block
61
62	// pos marks the end of plaintext in the buf
63	pos uint
64
65	// ctr is the number of blocks we have MAC'd so far
66	ctr uint
67
68	// finished is set true when we are done processing a message, and forbids
69	// any subsequent writes until we reset the internal state
70	finished bool
71}
72
73// New creates a new PMAC instance using the given cipher
74func New(c cipher.Block) hash.Hash {
75	if c.BlockSize() != block.Size {
76		panic("pmac: invalid cipher block size")
77	}
78
79	d := new(pmac)
80	d.c = c
81
82	var tmp block.Block
83	tmp.Encrypt(c)
84
85	for i := range d.l {
86		copy(d.l[i][:], tmp[:])
87		tmp.Dbl()
88	}
89
90	// Compute L(−1) ← L · x⁻¹:
91	//
92	//     a>>1 if lastbit(a)=0
93	//     (a>>1) ⊕ 10¹²⁰1000011 if lastbit(a)=1
94	//
95	copy(tmp[:], d.l[0][:])
96	lastBit := int(tmp[block.Size-1] & 0x01)
97
98	for i := block.Size - 1; i > 0; i-- {
99		carry := byte(subtle.ConstantTimeSelect(int(tmp[i-1]&1), 0x80, 0))
100		tmp[i] = (tmp[i] >> 1) | carry
101	}
102
103	tmp[0] >>= 1
104	tmp[0] ^= byte(subtle.ConstantTimeSelect(lastBit, 0x80, 0))
105	tmp[block.Size-1] ^= byte(subtle.ConstantTimeSelect(lastBit, block.R>>1, 0))
106	copy(d.lInv[:], tmp[:])
107
108	return d
109}
110
111// Reset clears the digest state, starting a new digest.
112func (d *pmac) Reset() {
113	d.digest.Clear()
114	d.offset.Clear()
115	d.buf.Clear()
116	d.pos = 0
117	d.ctr = 0
118	d.finished = false
119}
120
121// Write adds the given data to the digest state.
122func (d *pmac) Write(msg []byte) (int, error) {
123	if d.finished {
124		panic("pmac: already finished")
125	}
126
127	var msgPos, msgLen, remaining uint
128	msgLen = uint(len(msg))
129	remaining = block.Size - d.pos
130
131	// Finish filling the internal buf with the message
132	if msgLen > remaining {
133		copy(d.buf[d.pos:], msg[:remaining])
134
135		msgPos += remaining
136		msgLen -= remaining
137
138		d.processBuffer()
139	}
140
141	// So long as we have more than a blocks worth of data, compute
142	// whole-sized blocks at a time.
143	for msgLen > block.Size {
144		copy(d.buf[:], msg[msgPos:msgPos+block.Size])
145
146		msgPos += block.Size
147		msgLen -= block.Size
148
149		d.processBuffer()
150	}
151
152	if msgLen > 0 {
153		copy(d.buf[d.pos:d.pos+msgLen], msg[msgPos:])
154		d.pos += msgLen
155	}
156
157	return len(msg), nil
158}
159
160// Sum returns the PMAC digest, one cipher block in length,
161// of the data written with Write.
162func (d *pmac) Sum(in []byte) []byte {
163	if d.finished {
164		panic("pmac: already finished")
165	}
166
167	if d.pos == block.Size {
168		xor(d.digest[:], d.buf[:])
169		xor(d.digest[:], d.lInv[:])
170	} else {
171		xor(d.digest[:], d.buf[:d.pos])
172		d.digest[d.pos] ^= 0x80
173	}
174
175	d.digest.Encrypt(d.c)
176	d.finished = true
177
178	return append(in, d.digest[:]...)
179}
180
181func (d *pmac) Size() int { return block.Size }
182
183func (d *pmac) BlockSize() int { return block.Size }
184
185// Update the internal tag state based on the buf contents
186func (d *pmac) processBuffer() {
187	xor(d.offset[:], d.l[bits.TrailingZeros(d.ctr+1)][:])
188	xor(d.buf[:], d.offset[:])
189	d.ctr++
190
191	d.buf.Encrypt(d.c)
192	xor(d.digest[:], d.buf[:])
193	d.pos = 0
194}
195
196// XOR the contents of b into a in-place
197func xor(a, b []byte) {
198	for i, v := range b {
199		a[i] ^= v
200	}
201}
202