damaki/libkeccak

SHA-3 and other Keccak related algorithms in SPARK/Ada.

libkeccak's Issues

Incorrect parallel hash output when building with SSE2 instructions

When building with LIBKECCAK_ARCH=x86_64 and LIBKECCAK_SIMD=SSE2 the parallel hashes (ParallelHash, KangarooTwelve, etc) produce incorrect output. The known answer tests fail with the following output:

Loading file: testvectors/ParallelHash/ParallelHash128_samples.txt
Running 3 tests ...
FAILURE:
   Expected MD: BA8DC1D1D979331D3F813603C67F72609AB5E44B94A0B8F9AF46514454A2B4F5
   Actual MD:   3E5AC8757659890646FC627DC8EC9DA8019E150CA203566AA42C1955564787BE
FAILURE:
   Expected MD: FC484DCB3F84DCEEDC353438151BEE58157D6EFED0445A81F165E495795B7206
   Actual MD:   B5236BC97DCC088B6A2A9D87BB0AD11F2A8ACE1143F73FBC8582987EFC5FC0B8
FAILURE:
   Expected MD: F7FD5312896C6685C828AF7E2ADB97E393E7F8D54E3C2EA4B95E5ACA3796E8FC
   Actual MD:   245C4A5FA512F7AAE3D33B6A3A8E2EB26A8026EC1909B7B3FE79EC3F09CD6635

Passed: 0
Failed: 3

The problem is only present when using SSE2; it is not present when building with LIBKECCAK_SIMD=AVX2 or LIBKECCAK_SIMD=none.

The problem is due to an incorrect definition of KeccakF_1600_P2 in src/x86_64/SSE2/keccak-parallel_keccak_1600.ads where it is defined as follows:

   package KeccakF_1600_P2 is new Keccak.Generic_Parallel_KeccakF
     (Lane_Size_Log => 6,
      Lane_Type     => Interfaces.Unsigned_64,
      VXXI_Index    => Arch.SSE2.V2DI_Vectors.V2DI_Index,
      VXXI          => Arch.SSE2.V2DI_Vectors.V2DI,
      VXXI_View     => Arch.SSE2.V2DI_Vectors.V2DI_View,
      Vector_Width  => 2,
      Load          => Arch.SSE2.V2DI_Vectors.Load,
      Store         => Arch.SSE2.V2DI_Vectors.Store,
      "xor"         => Arch.SSE2.V2DI_Vectors."xor",
      Rotate_Left   => Arch.SSE2.V2DI_Vectors.Shift_Left,
      And_Not       => Arch.SSE2.V2DI_Vectors.And_Not,
      Shift_Left    => Interfaces.Shift_Left,
      Shift_Right   => Interfaces.Shift_Right);

The Rotate_Left generic parameter is incorrectly set to Arch.SSE2.V2DI_Vectors.Shift_Left instead of Arch.SSE2.V2DI_Vectors.Rotate_Left.

Remove dependency on gnatprove in the top-level alire.toml

The top-level alire.toml for libkeccak should not depend directly on gnatprove

The recommended workflow is to have a nested crate that depends on libkeccak and on gnatprove, that is used for the verification. This nested crate needs not to be explicitly published, but can be distributed normally with the main library sources. See here: https://github.com/alire-project/alire/blob/master/doc/catalog-format-spec.md#using-pins-for-crate-testing

Add design documentation

Libkeccak has grown to be a fairly large library with several cryptographic constructions, and the relationships between the modules are not immediately obvious without knowledge of the underlying cryptography. Documentation should be written to help users and reviewers understand the design of the library.

Support for GNATStack analysis please

Could we add
-fcallgraph-info=su,da
-fstack-usage

to the standard compiler options to enable GNATStack analysis please?

Compilation failures with GNAT Community 2020

Building libkeccak with the newly released GNAT Community 2020 results in compilation failures:

gprbuild -d -Plibkeccak.gpr -p
Compile
   [Ada]          keccak-parallel_keccak_1600.ads
   [Ada]          keccak-parallel_keccak_1600-rounds_24.ads
   [Ada]          keccak-parallel_keccak_1600-rounds_14.ads
   [Ada]          keccak-parallel_keccak_1600-rounds_12.ads
   [Ada]          tuple_hash.ads
   [Ada]          shake.ads
   [Ada]          sha3.ads
   [Ada]          rawshake.ads
   [Ada]          parallel_hash.ads
   [Ada]          marsupilamifourteen.ads
   [Ada]          kmac.ads
   [Ada]          ketje.ads
   [Ada]          keccak.ads
   [Ada]          keccak-util.adb
   [Ada]          keccak-types.ads
keccak-generic_monkeyduplex.ads:55:19: not subtype conformant with declaration at ketje.ads:66
keccak-generic_monkeyduplex.ads:55:19: formal subprograms are not subtype conformant (RM 6.3.1 (17/3))
keccak-generic_monkeyduplex.ads:55:19: not subtype conformant with declaration at ketje.ads:96
keccak-generic_monkeyduplex.ads:55:19: formal subprograms are not subtype conformant (RM 6.3.1 (17/3))
keccak-generic_monkeyduplex.ads:55:19: not subtype conformant with declaration at ketje.ads:126
keccak-generic_monkeyduplex.ads:55:19: formal subprograms are not subtype conformant (RM 6.3.1 (17/3))
keccak-generic_monkeyduplex.ads:55:19: not subtype conformant with declaration at ketje.ads:156
keccak-generic_monkeyduplex.ads:55:19: formal subprograms are not subtype conformant (RM 6.3.1 (17/3))
keccak-generic_monkeywrap.ads:62:04: instantiation error at keccak-generic_monkeyduplex.ads:55
keccak-generic_monkeywrap.ads:62:04: not subtype conformant with declaration at ketje.ads:66
keccak-generic_monkeywrap.ads:62:04: formal subprograms are not subtype conformant (RM 6.3.1 (17/3))

   compilation of ketje.ads failed

These compilation errors seem to be caused by a clash between subprograms with the same name in certain scopes.

For example, in ketje.ads there are lines such as (some parameters omitted for clarity):

      procedure XOR_Padding_Into_State is new Keccak.Padding.XOR_Pad101_Into_State
        (...)

      package MonkeyDuplex_Jr is new Keccak.Generic_MonkeyDuplex
        (...
         XOR_Padding_Into_State => XOR_Padding_Into_State,
         ...)

The compilation error seems to be that the declaration of XOR_Padding_Into_State clashes with the generic formal parameter of Generic_MonkeyDuplex of the same name. Renaming the XOR_Padding_Into_State procedure to something else avoids the problem.

All instances of this compilation error should be fixed by renaming functions as appropriate.

Github does not recognize the license

Github does not recognize the license (it shows "View license" instead of "BSD-3-Clause" and no license information when you view the file) because of the different word wrapping.

You can easily fix this by editing the LICENSE file and the click on "Choose a license template" in the upper right corner and then choose "BSD 3-Clause "New" or "Revisded" License" on the left.

Compilation errors with GCC 12

When building libkeccak with GCC 12.2.1 with SSE2 and/or AVX2 intrinsics enabled (via LIBKECCAK_SIMD) the compilation fails with the following errors:

keccak-arch-sse2.ads:68:16: error: intrinsic binding type mismatch on result
keccak-arch-sse2.ads:72:16: error: intrinsic binding type mismatch on result
keccak-arch-sse2.ads:72:16: error: intrinsic binding type mismatch on result
keccak-arch-sse2.ads:72:16: error: intrinsic binding type mismatch on result

The command line used is:

alr build -- -XLIBKECCAK_ARCH=x86_64 -XLIBKECCAK_SIMD=AVX2

Parallel hashes crash when built with AVX2 on Windows.

Description:
When libkeccak is built on Windows with AVX2 instructions enabled (ARCH=x86_64 and SIMD=AVX2) parallel hashes (KangarooTwelve, ParallelHash, etc) crash with a Program_Error raised with EXCEPTION_ACCESS_VIOLATION as the message when processing input data or generate output data. This only occurs if the data input/output buffer is large enough to trigger the usage of AVX2 instructions.

The problem has only been observed on Windows. Builds on Linux using the same version of the compiler (GNAT Community 2019) are confirmed to be working at the time of writing.

Steps to reproduce:
Compiler version: 64-bit GCC 8.3.1 20190518 (for GNAT Community 2019 20190517)
Operating system: Windows

1. On Windows, run make test ARCH=x86_64 SIMD=AVX2
2. The crash occurs when the tests are run.

Workaround:
The workaround is to avoid building libkeccak with AVX2 on Windows. Instead, use SSE2 instructions only, i.e. build libkeccak with ARCH=x86_64 SIMD=SSE2. This will result in slightly lower performance compared to AVX2, but is still pretty fast and at least it doesn't crash.

Root cause:
The root of the problem is that GCC is not respecting the requested 32-byte alignment on objects of type Keccak.Arch.AVX2.V4DI_Vectors.V4DI allocated on the stack, but is still generating AVX2 instructions (i.e. vmovdqa) which assume 32-byte alignment. This attempt to load/store misaligned data on the stack is causing the segfault in the AVX2 instantiations of Keccak.Generic_Parallel_Keccakf.Permute_All.

By contrast, on Linux GCC adjusts the stack pointer to ensure it is 32-byte aligned with the following disassembly:

   0x000000000040ecf0 <+0>:    push   %rbp
   0x000000000040ecf1 <+1>:    mov    $0x432540,%eax
   0x000000000040ecf6 <+6>:    mov    $0x4326c0,%edx
   0x000000000040ecfb <+11>:    mov    %rsp,%rbp
   0x000000000040ecfe <+14>:    and    $0xffffffffffffffe0,%rsp
   0x000000000040ed02 <+18>:    sub    $0x368,%rsp

The disassembly of the same function when built on Windows with the same version of GNAT does not align the stack pointer:

   0x0000000000452e50 <+0>:     sub    $0x468,%rsp

This seems to be a known bug in 64-bit GCC Windows, judging by the following links:

• https://stackoverflow.com/questions/5983389/how-to-align-stack-at-32-byte-boundary-in-gcc
• https://gcc.gnu.org/bugzilla/show_bug.cgi?id=49001