EuCrypt: Correcting Bounds Error in Keccak (Word-Level)



March 3rd, 2018 by Diana Coman

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

Thanks to prompt use of Keccak as hashing method in the new vtools by phf , an error has been discovered and neatly reported1 about 8 hours ago. Thanks to the very helpful way in which the error was reported and the very helpful way in which Ada reports the very line on which some check failed, it took all of 10 minutes to identify the problem: I had flipped 2 variables, attempting to copy from "ToPos" to "FromPos" and somehow I failed to see this glaring error even at re-readings... Other than the obvious fact that I should take a break, get more sleep and all that, there really is nothing else I can say on how this happened. So I'll get straight on to the fix for the error itself, meaning changing one line in eucrypt/smg_keccak/smg_keccak.adb:

-      BWord(Bitword'First .. Bitword'First + SBB - 1) := Block(ToPos..FromPos);
+      BWord(Bitword'First .. Bitword'First + SBB - 1) := Block(FromPos..ToPos);

Note that the bit-level Keccak will not have this sort of problem as it doesn't have to dance around the "is it multiple of 8 or not?" issue that required the above code in the first place in the word-level version. So there is nothing to change in the bit-level Keccak.

As usual, an error found means at least one test added to first show the error and then showcase the result of the fix. In this case the test has been basically already provided by the helpful phf. I have simply adapted it to make it use the full valid range of the bitrate for Keccak (based on the Keccak_Rate type defined in smg_keccak.ads) and to actually fail if there is a problem anywhere, since the failure itself will be pointing precisely at where the trouble is. The new test is added to eucrypt/smg_keccak/tests/smg_keccak-test.adb:

+  procedure test_all_bitrates is
+    Input : constant String := "hello, world";
+    Bin   : Bitstream( 0 .. Input'Length * 8 - 1 ) := ( others => 0 );
+    Bout  : Bitstream( 0 .. 100 ) := ( others => 0 );
+  begin
+    ToBitstream( Input, Bin );
+    Put_Line("Testing all bitrates:");
+      for Bitrate in Keccak_Rate'Range loop
+        Sponge(Bin, Bout, Bitrate);
+        Put_Line("PASSED: keccak with bitrate " & Integer'Image(Bitrate));
+      end loop;
+  end test_all_bitrates;
+

Running all the tests shows now a very satisfying PASSED for ALL valid bitrates of Keccak. Note that bitrate has to be between 1 and width of the Keccak state, which is currently 1600. Anything outside this range will cause CORRECTLY an abortion of execution - this will happen however as soon as the Sponge procedure is called since the value will simply not match the restricted Keccak_Rate type.

The .vpatch for the above and its signature will be on my Reference Code Shelf as well as linked here directly for your convenience:


  1. Reported with code to reproduce the problem and a paste of the output and everything one needs to find the trouble in about 10 minutes flat. 

Comments feed: RSS 2.0

One Response to “EuCrypt: Correcting Bounds Error in Keccak (Word-Level)”

  1. […] of EuCrypt must be pulled in, or a new patch must be created off of the smg-keccak branch to correct the trouble. I want esthlos-v to be as small 1 and simple 2 as possible, so pulling in all of […]

Leave a Reply