m
to Bobm
generated by Alice will be accepted by Bob
m'
generated by EveDiagram:
m, t = MAC(k, m)
Alice * Bob
k \> Eve k
t = MAC(k, m)
k
, so she can'tTo verify a message m'
with tag t
, Bob can simply compute t' = MAC(k, m')
and check
that t'
is equal to t
. As long as only Alice and Bob have k
, Bob is sure alice
sent m'
m
with probability 2^l(t)
, where
l(t)
is the length of the MACAdversarial model:
m
=>
gets a list (m, MAC(k, m))
for m
's chosen by her(m', T)
that Bob will accept2^l(t) + negl(l(t))
PRFMAC(k, m) = h(k  m), where h is a random oracle
In practice we don't have a random oracle, and iterative hash functions are
susceptible to lengthextension attacks where if you have
h(k  m)
you can compute h(k  m  extension)
without knowing k
Diagram:
m1 m2 m3
\ \ \
o > + > + > ... > +
\  \  \
k > E  E  k'> E
    \
  tag
where k' = f(k), f is a constant function
PRFMAC
is susceptible toHMAC(k, m) = h(k_1  h (k_2  m))
, where
k_1 = k \xor opad
k_2 = k \xor ipad
We saw with encryption that we have informationtheoretic secure encryption like the onetime pad.
Can we also have an informationtheoretic secure onetime MAC?
Table:
confidentiality  integrity

unconditional OTP  OTMac
conventional block ciphers  MACs
publickey PK encryption  digital signatures
m
are confidentialh
(headers?) that need integrity Alice computes:
c = Enc(k_1, m)
T = MAC(k_2, h  c)
transmit header h, c, t
Bob concatenates h  c and computes t' = MAC(k_2, h  c),
checks that t = t', and if true, decrypt m = Dec(k_1, c)
Note: Applying a MAC to the plaintext instead of the ciphertext can be a bad idea because the MAC could leak plaintext information
t
Notes:
m
and one for MACing c
Nonce N
:
N
is pseudorandomDiagram:
N M H
\ \ 
k > MAC1 k > CTR k > MAC2
 /  
 c /  
*/  
 \ 
  
  ctext  
  
  
 k > MAC3 
  
  
+

\
tag
Note:
MACi(k, m) = MAC(k, i  m)
Definition: (S, +, *)
, where:
S
is finite,(S, +)
is an abelian (commutative) group with identity zero
a + (b + c) = (a + b) +c
a + 0 = 0 + a = a
\forall a, \exists b, s.t. a + b = 0
b = a^1
(S*, *)
is an abelian group with identity one
S* = S  {0}
a*(b+c) = a*b + a*c
(b+c)*a = b*a + c*a
GF(p)
 finite fields (a.k.a. Galois fields) on p
elements {0, 1, ..., p1}
ax + b = 0 (mod p) =>
x = b * a^1
3x + 5 = 6 (mod 7) =>
3x = 1 (mod 7) => (5 = 3^1 (mod 7))
x = 5
GF(q)
finite field where S = q
. When do finite fields exists, for what q's
?
Theorem: GF(q)
exists iff q = p^k
for some prime p, k >= 1
(see here for more info)
TODO: Proof:
How do we create a GF(p^k)
field, where k > 1
?
We work with (univariate) polynomials of degree < k
with coefficients in GF(p)
f(x) = a_k1 x^k1 + a_k2 x^k2 + ... + a_1 x + a0
There are k
coefficients, so there's p^k
such polynomials, => p^k
elements in S

Does it respect the definition of a field?
k
Example: GF(4) = GF(2^2), p = 2, k = 2
is the set of univariate polynomials of
degree < 2
with coefficients in GF(2)
. Thus GF(4)
has 4 polynomials (4 elements):
0
1
x
x + 1
Multiplying them, we work modulo p(x) = x^2 + x + 1, p(x) = 0 => x^2 = x1 => (in GF(2) x = x, 1 = 1) => x^2 = x + 1
*  0 1 x x+1

0  0 0 0 0
1  0 1 x x+1
x  0 x x+1 1
x+1  0 x+1 1 x
x * x = x^2 = x+1
x * (x + 1) = x^2 + x = (x+1) + x = 1
(x+1)(x+1) = x^2 + x + x + 1 = x^2 + 1 = (x+1) + 1 = x
How do we choose the modulo x^2 + x + 1
? Gotta make sure they are irreducible.
What about division?
We want to compute a^b
, b
is an integer, a
is a number in your finite field
{ 1, if b = 0
{
a^b = { (a^(b/2))^2 if b = even
{
{ a*a^(b1) if b = odd
We have to do <= 2*log_2(b)
multiplications
If b
is secret, this can be problematic because the runtime is dependent on the value of b
.
Fermat's little theorem (FLT): In GF(q)
for all a \in GF(q)*
, we have a^(q1) = 1
, where 1 is the multiplicative identity in GF(q)
Corallary: For all a \in GF(q)
, we have a^q = a
Corallary: For all a \in GF(q)
, we have a^1 = a^(q2)
Example:
3^1 (mod 7) = 3^5 = 27 * 9 = 6 * 2 = 12 = 5