Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

i wrote this code:

// integer is a drop-in replacement of standard int
// http://calccrypto.wikidot.com/programming:integer
// it is an arbitrary precision intger
// integer::str(base, size) returns a string in that base, 'size' long padding the front with 0s
// base 256 means an ASCII string: 24930 (base 10) = "ab" (base 256)

// CRYPT::AES is from another library i wrote, which is correct, so its correctness
// is irrelevant to this post

static const std::string zeros(16, 0);
static const integer mask(std::string(16, 0xff), 256); // instead of mod 2^128, i do & 2^128 - 1

std::pair <integer, integer> Generate_Subkey(std::string & key){
    integer L(CRYPT::AES(key).encrypt(zeros), 256);
    std::pair <integer, integer> k;
    L <<= 1;
    k.first = L;
    if (k.first[128])
        k.first ^= 0x87;
    L <<= 1;
    k.second = L;
    if (k.first[127])
        k.second ^= 0x87;
    k.first &= mask;
    k.second &= mask;
    return k;
}

std::string AES_CMAC(std::string key, std::string message){
    std::pair <integer, integer> K = Generate_Subkey(key);
    if (message.size() && !(message.size() & 15))
        message = message.substr(0, message.size() - 16) + (integer(message.substr(message.size() - 16, 16), 256) ^ K.first).str(256, 16);
    else if (!message.size() || (message.size() & 15)){
        message += "\x80";
        while (message.size() & 15)
            message += std::string(1, 0);
        message = message.substr(0, message.size() - 16) + (integer(message.substr(message.size() - 16, 16), 256) ^ K.second).str(256, 16);
    }
    integer X;
    CRYPT::AES aes(key);
    while (message.size()){
        integer Y = X ^ integer(message.substr(0, 16), 256);
        X = integer(aes.encrypt(Y.str(256, 16)), 256);
        message = message.substr(16, message.size() - 16);
    }
    return X.str(256, 16);
}

std::string AES_CMAC_96(std::string key, std::string message){
    return AES_CMAC(key, message).substr(0, 12);
}

std::string AES_CMAC_PRF_128(std::string key, std::string message){
    if (key.size() != 16)
        key = AES_CMAC(zeros, key);
    return AES_CMAC(key, message);
}

in accordance with RFCs 4493, 4494, and 4615 (with some small optimizations).

They seems straightforward enough, specifically saying that RFC 4493 is the core of the other two, and all of the functions being rather simple to implement.

From the RFCs:

   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   +                    Algorithm Generate_Subkey                      +
   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   +                                                                   +
   +   Input    : K (128-bit key)                                      +
   +   Output   : K1 (128-bit first subkey)                            +
   +              K2 (128-bit second subkey)                           +
   +-------------------------------------------------------------------+
   +                                                                   +
   +   Constants: const_Zero is 0x00000000000000000000000000000000     +
   +              const_Rb   is 0x00000000000000000000000000000087     +
   +   Variables: L          for output of AES-128 applied to 0^128    +
   +                                                                   +
   +   Step 1.  L := AES-128(K, const_Zero);                           +
   +   Step 2.  if MSB(L) is equal to 0                                +
   +            then    K1 := L << 1;                                  +
   +            else    K1 := (L << 1) XOR const_Rb;                   +
   +   Step 3.  if MSB(K1) is equal to 0                               +
   +            then    K2 := K1 << 1;                                 +
   +            else    K2 := (K1 << 1) XOR const_Rb;                  +
   +   Step 4.  return K1, K2;                                         +
   +                                                                   +
   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   +                   Algorithm AES-CMAC                              +
   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   +                                                                   +
   +   Input    : K    ( 128-bit key )                                 +
   +            : M    ( message to be authenticated )                 +
   +            : len  ( length of the message in octets )             +
   +   Output   : T    ( message authentication code )                 +
   +                                                                   +
   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   +   Constants: const_Zero is 0x00000000000000000000000000000000     +
   +              const_Bsize is 16                                    +
   +                                                                   +
   +   Variables: K1, K2 for 128-bit subkeys                           +
   +              M_i is the i-th block (i=1..ceil(len/const_Bsize))   +
   +              M_last is the last block xor-ed with K1 or K2        +
   +              n      for number of blocks to be processed          +
   +              r      for number of octets of last block            +
   +              flag   for denoting if last block is complete or not +
   +                                                                   +
   +   Step 1.  (K1,K2) := Generate_Subkey(K);                         +
   +   Step 2.  n := ceil(len/const_Bsize);                            +
   +   Step 3.  if n = 0                                               +
   +            then                                                   +
   +                 n := 1;                                           +
   +                 flag := false;                                    +
   +            else                                                   +
   +                 if len mod const_Bsize is 0                       +
   +                 then flag := true;                                +
   +                 else flag := false;                               +
   +                                                                   +
   +   Step 4.  if flag is true                                        +
   +            then M_last := M_n XOR K1;                             +
   +            else M_last := padding(M_n) XOR K2;                    +
   +   Step 5.  X := const_Zero;                                       +
   +   Step 6.  for i := 1 to n-1 do                                   +
   +                begin                                              +
   +                  Y := X XOR M_i;                                  +
   +                  X := AES-128(K,Y);                               +
   +                end                                                +
   +            Y := M_last XOR X;                                     +
   +            T := AES-128(K,Y);                                     +
   +   Step 7.  return T;                                              +
   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   +                    Algorithm AES-CMAC-96                          +
   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   +                                                                   +
   +   Input    : K (128-bit Key described in Section 4.1)             +
   +            : M    (message to be authenticated)                   +
   +            : len  (length of message in octets)                   +
   +   Output   : Truncated T  (truncated output to length 12 octets)  +
   +                                                                   +
   +-------------------------------------------------------------------+
   +                                                                   +
   +   Step 1.  T  := AES-CMAC (K,M,len);                              +
   +   Step 2.  TT := truncate (T, 12);                                +
   +            return TT;                                             +
   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   +                        AES-CMAC-PRF-128                           +
   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
   +                                                                   +
   + Input  : VK (Variable-length key)                                 +
   +        : M (Message, i.e., the input data of the PRF)             +
   +        : VKlen (length of VK in octets)                           +
   +        : len (length of M in octets)                              +
   + Output : PRV (128-bit Pseudo-Random Variable)                     +
   +                                                                   +
   +-------------------------------------------------------------------+
   + Variable: K (128-bit key for AES-CMAC)                            +
   +                                                                   +
   + Step 1.   If VKlen is equal to 16                                 +
   + Step 1a.  then                                                    +
   +               K := VK;                                            +
   + Step 1b.  else                                                    +
   +               K := AES-CMAC(0^128, VK, VKlen);                    +
   + Step 2.   PRV := AES-CMAC(K, M, len);                             +
   +           return PRV;                                             +
   +                                                                   +
   +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

this code will generate the correct MAC values for every test vector provided in the 3 RFCs (as well as MACs I found from other sources) except for

   Test Case AES-CMAC-PRF-128 with 20-octet input
   Key        : 00010203 04050607 08090a0b 0c0d0e0f edcb
   Key Length : 18
   Message    : 00010203 04050607 08090a0b 0c0d0e0f 10111213
   PRF Output : 84a348a4 a45d235b abfffc0d 2b4da09a

   Test Case AES-CMAC-PRF-128 with 20-octet input
   Key        : 00010203 04050607 08090a0b 0c0d0e0f
   Key Length : 16
   Message    : 00010203 04050607 08090a0b 0c0d0e0f 10111213
   PRF Output : 980ae87b 5f4c9c52 14f5b6a8 455e4c2d

in RFC 4615. I dont understand why. What did I do wrong? AES-CMAC-PRF-128 is simply AES-CMAC with a single extra if statement, and yet i bungled this implementation.

Is it possible that this RFC is wrong?

share|improve this question
add comment

1 Answer 1

up vote 5 down vote accepted

Hmmm, I think I might see the problem. In Generate_Subkey(), you have:

L <<= 1;
k.first = L;
if (k.first[128])
    k.first ^= 0x87;
L <<= 1;
k.second = L;
if (k.first[127])
    k.second ^= 0x87;

This sets K2 to either L << 2 or (L << 2) XOR const_Rb.

On the other hand, the pseudocode has

+   Step 2.  if MSB(L) is equal to 0                                +
+            then    K1 := L << 1;                                  +
+            else    K1 := (L << 1) XOR const_Rb;                   +
+   Step 3.  if MSB(K1) is equal to 0                               +
+            then    K2 := K1 << 1;                                 +
+            else    K2 := (K1 << 1) XOR const_Rb;                  +

This sets K2 to either K1 << 1 or (K1 << 1) XOR const_Rb

They differ when K1 $\ne$ (L << 1), that is, if the original (k.first[128]) test was true.

This problem would cause half the keys to work just like the test vectors say that should, and half the keys not to work at all.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.