EuCrypt: Correcting an Error in OAEP Check

~ This is part of the EuCrypt series. Start with Introducing EuCrypt. ~

As I was (re)reading today through my own OAEP with Keccak code from the previous chapter, I found an error1. And while I take all the blame for it being there in the first place and for it remaining there for all of 5 days until today, I have to take also all the credit for finding it and fixing it. There is power in all the numbers, including one, apparently. Without further talk, let's see the error itself, in eucrypt/smg_keccak/smg_oaep.adb:

MaxLen       : constant Natural := OAEP_LENGTH_OCTETS - 11;

That MaxLen is the maximum length of plain text that can fit in a single OAEP block (hence, the maximum number of characters that can be encrypted with a single call to OAEP_Encrypt and at the same time the maximum number of characters that OAEP_Decrypt can ever return as decrypted message). It is used later on in the OAEP_Decrypt procedure to do a basic validity check on the "decrypted" message: if the length as read from the decrypted OAEP block is higher than this MaxLen then there is clearly something wrong (corrupt/invalid OAEP block most likely) and the procedure simply sets the success flag to "False" without any further operations (avoiding thus among other things attempts to read outside the bounds of the arrays involved for instance). The error in the above line is the use of OAEP_LENGTH_OCTETS which stands for the length in octets of the whole, encrypted OAEP block. The correct calculation has to be made either with OAEP_LENGTH_OCTETS/2 or more directly with the actual constant defined precisely for this purpose and otherwise used correctly at OAEP_Encrypt: OAEP_HALF_OCTETS. So the correct line is:

MaxLen       : constant Natural := OAEP_HALF_OCTETS - 11;

Before actually making that change in code however, the very first thing to do in such a case is a... test that exposes this type of issue. As current tests really are absolutely minimal, there can't be a better time than right now to add to them anyway so here are 2 additional tests that use OAEP_Decrypt on invalid input and, respectively, both encrypt and decrypt on an initial message longer than the maximum length (eucrypt/smg_keccak/tests/smg_keccak-test.adb):

    -- test decrypt on invalid (non-OAEP) string
    Flag := True;
    C := Encr( Encr'First );
    Encr( Encr'First ) := Character'Val( Character'Pos( C ) / 2 );
    Decr := ( others => ' ' );
    OAEP_Decrypt( Encr, Len, Decr, Flag );

    if Flag = True then
      Put_Line("FAILED: oaep test with invalid package");
      Put_Line("PASSED: oaep test with invalid package");
    end if;

    -- test encrypt on message longer than maximum payload (1096 bits)
    Flag := False;
    Len := 0;
    LongMsg( 1..Msg'Length ) := Msg;
    Encr := ( others => '.' );
    OAEP_Encrypt( LongMsg, Entropy, Encr);
    OAEP_Decrypt( Encr, Len, Decr, Flag);

    if Flag = False or
       Len /= MaxLen * 8 or
       Decr( Decr'First .. Decr'First + Len / 8 - 1 ) /=
             LongMsg( LongMsg'First..LongMsg'First + MaxLen - 1 )
      Put_Line("FAILED: oaep test with too long message");
      Put_Line("Msg is: "  & LongMsg);
      Put_Line("Decr is: " & Decr);
      Put_Line("Flag is: " & Boolean'Image( Flag ) );
      Put_Line("Len is: "  & Natural'Image( Len ) );
      Put_Line("PASSED: oaep test with too long message");
    end if;

The first test basically messes one character from a valid OAEP-encrypted string and then tries to pass the result on to the OAEP_Decrypt procedure. The test fails if the success flag is set to true (since that means OAEP_Decrypt reports success on an invalid packet). The second test provides an initial plain-text message longer than the maximum length and checks that OAEP uses indeed only the first MaxLen bits ignoring the rest, as stated in the procedure's own description of behaviour (see the relevant comments in the code).

Running the above tests with the original code results, as expected, in trouble. However, having used the very reliable Ada language means that the code fails very clearly and obviously: as the length is greater than the available space, the boundary checks fail and the execution is aborted. Once the error is corrected, the code recompiled and the tests run again, the execution proceeds correctly and all the tests (new and old) pass as expected.

Digging a bit deeper into this reveals that there is scope for further improving the code itself to limit the opportunity for such mistake in the future: the MaxLen value is in fact a constant shared by all the OAEP procedures. Consequently, MaxLen should be MAX_LEN_MSG, defined right under OAEP_LENGTH_OCTETS and the others, together with its supporting "TMSR" string, like this:

  TMSR               : constant String := "TMSR-RSA";
  MAX_LEN_MSG        : constant := OAEP_HALF_OCTETS - TMSR'Length - 3;

And since I'm doing some refactoring essentially, I further take this chance to also remove a few prints (Put_Line in Ada's terms) from the oaep tests: the reason for removing them is that they are not of much help when the tests pass anyway (and if the tests fail you'll need to dig deeper than looking at those prints anyway) and moreover, they can mess up your console since they effectively print as characters the gobbledygook resulting from OAEP encrypt. When all is finished, it's time to run all tests again and make sure they all pass.

The .vpatch for all the above changes and refactoring (including updating comments as needed to reflect the removal of MaxLen and the new MAX_LEN_MSG), together with my signature for it will live like all the other EuCrypt .vpatches on my Reference Code Shelf. For your convenience, I link here as well the full .vpatch and my signature for it:

As a fitting ending to this unexpected but necessary post in the EuCrypt series, I'll just link here for comparison the story of the last time I had to correct an error as part of this EuCrypt series: the MPI error that survived for years and was finally uncovered hidden under the carpet. I'll let my readers compare the respective lives of the two errors and the three involved corrections. Meanwhile, I'll just get back to work on the next EuCrypt chapter that will be published as usual, on Thursday.

  1. No, not a "bug", not a "silly mistake" nor anything else but exactly what it is: an error. My error, too.  

Leave a Reply