manbytesgnu_site

Source files for manbytesgnu.org
git clone git://holbrook.no/manbytesgnu_site.git
Log | Files | Refs

20210418_keccak.rst (4242B)


      1 In search of a slim KECCAK dependency
      2 #####################################
      3 
      4 :date: 2021-04-18 15:01
      5 :modified: 2021-04-18 19:48
      6 :category: Code
      7 :author: Louis Holbrook
      8 :tags: crypto,hash,keccak,sha3,python,c
      9 :slug: keccak-benchmarks
     10 :summary: Compare performance and sizes of alternative KECCAK SHA3 implementations
     11 :lang: en
     12 :status: draft
     13 
     14 Implementations
     15 ===============
     16 
     17 XKCP
     18 ----
     19 
     20 - Site: https://keccak.team/keccak_specs_summary.html
     21 - Code: https://github.com/xkcp/xkcp
     22 - Git hash: c438ee7b2736726f629da11b7012cffcf6b84fef
     23 
     24 
     25 .. include:: code/keccak-benchmarks/XKCP/small.c
     26    :code: c
     27    :number-lines: 0
     28 
     29 .. include:: code/keccak-benchmarks/XKCP/bench.c
     30    :code: c
     31    :number-lines: 0
     32 
     33 
     34 keccak_tiny
     35 -----------
     36 
     37 - Code: https://github.com/coruus/keccak-tiny
     38 - Git hash: 64b6647514212b76ae7bca0dea9b7b197d1d8186
     39 
     40 Needed to export `hash` function symbol, and add to header file.
     41 
     42 
     43 tiny_sha3 
     44 ---------
     45 
     46 - Code [1]_: https://github.com/mjosaarinen/tiny_sha3 
     47 - Git hash: dcbb3192047c2a721f5f851db591871d428036a9
     48 
     49 Had to change "padding" value in ``sha3.c``
     50 
     51 .. code-block:: c
     52    :linenos: table
     53    :linenostart: 142
     54 
     55         c->st.b[c->pt] ^= 0x01;
     56 
     57 .. code-block:: c
     58 
     59         sha3(data, 3, buf, 32);
     60 
     61 libkeccak
     62 ---------
     63 
     64 - Code: https://github.com/maandree/libkeccak
     65 - Git hash: 718b1a6ea1c44bcf15e55d3c265310e1cd9211fa
     66 
     67 .. code-block:: bench.c
     68 
     69         libkeccak_state_initialise(&state, &spec);
     70         libkeccak_fast_update(&state, msg, 3);
     71         libkeccak_fast_digest(&state, NULL, 0, 0, NULL, buf);
     72 
     73 
     74 Results
     75 =======
     76 
     77 - Input: "foo"
     78 - Rounds: 100000
     79 
     80 ..
     81         :XKCP generic64:
     82                 - Time: 0.041101298
     83                 - Executable size: 37768
     84                 - Archive size: 358558
     85 ..
     86         :keccak-tiny:
     87                 - Time: 0.046095483
     88                 - Executable size: 49400
     89                 - Object size: 35544
     90 ..
     91         :tiny_sha3 [1]_:
     92                 - Time: 0.080156921
     93                 - Executable size: 16577
     94                 - Object size: 6712
     95 ..
     96         :libkeccak:
     97                 - Time: 0.200222898
     98                 - Executable size: 50152
     99                 - Archive size: 78680 
    100 
    101 ==============  =============== ===============
    102 Implementation  Execution time  Executable size
    103 ==============  =============== ===============
    104 XKCP            **0.041101298** 37768
    105 keccak-tiny     0.046095483     49400
    106 tiny_sha3       0.080156921     **16577**
    107 libkeccak       0.200222898     50152
    108 ==============  =============== ===============
    109 
    110         .. [1] Author claims it is not suited for production
    111 
    112 Python
    113 ======
    114 
    115 XKCP has a pure-python implementation, but it's hopelessly slow. 
    116 
    117 Added to ``CompactFIPS202.py``:
    118 
    119 .. code-block:: python
    120 
    121         if __name__ == '__main__':
    122                 for i in range(10):
    123                 a = Keccak(1088, 512, b'foo', 0x01, 32)
    124 
    125                 for j in range(1,4):
    126                         a = 10**j
    127                         start_time = time.clock_gettime_ns(time.CLOCK_PROCESS_CPUTIME_ID)
    128                         for i in range(a):
    129                                 b = Keccak(1088, 512, b'foo', 0x01, 32)
    130                         end_time = time.clock_gettime_ns(time.CLOCK_PROCESS_CPUTIME_ID)
    131                         print(a, (end_time - start_time) / (10**9))
    132 
    133 ::
    134 
    135         $ python CompactFIPS202.py 
    136         10 0.007536721
    137         100 0.066636149
    138         1000 0.64519725
    139 
    140 
    141 Wrapping keccak_tiny
    142 --------------------
    143 
    144 Implementing ``XKCP`` in Python means creating two classes for the state and sponge structs. ``keccak_tiny`` is much simpler because it is merely a function call with a couple of char buffers. But with ctypes ends up being very slow, too. [2]_
    145 
    146 .. include:: code/keccak-benchmarks/keccak-tiny/wrap.py
    147    :code: python
    148    :number-lines: 0
    149 
    150 ::
    151         
    152         $ gcc -L. -D"memset_s(W,WL,V,OL)=memset(W,V,OL)" -shared keccak-tiny.c -o libkeccaktiny.so
    153         $ LD_LIBRARY_PATH=. python wrap.py
    154         0.95114457
    155         41b1a0649752af1b28b3dc29a1556eee781e4a4c3a1f7f53f90fa834de098c4d
    156 
    157         
    158 
    159 Compare with ``pysha3``:
    160 
    161 
    162 .. code-block:: python
    163      
    164         import sha3 
    165         h = sha3.keccak_256()
    166         h.update(b'foo')
    167         b = h.digest()
    168 
    169 ::
    170 
    171         0.162829927
    172 
    173 
    174 ..
    175 
    176         .. [2] for some reason when on battery; 1.74030088
    177