eqaf

Constant-time equal function on string
README

From some crypto libraries like
digestif or
Callipyge, it needed to have a
constant time equal function to avoid timing attacks. To avoid replication of
code and ensure maintainability of this kind of function, we decide to provide a
little package which implements equal function on string.

This library provides a benchmark to see if the equal function really has a
constant-time execution. We compare it with C implemention, Stdlib
implementation and some others impl. (like with nativeint or int64).

Benchmarks provides this kind of result:

- ########## Random ##########
- ---------- eqst ----------
- min:       0.002770.
- max:       0.150592.
- mean:      0.143873.
- median:    0.147260.
- deviation: 0.143137.
- deviation: 0.000206%.
- ---------- eqml ----------
- min:       0.000148.
- max:       0.000156.
- mean:      0.000153.
- median:    0.000153.
- deviation: 0.001563.
- deviation: 0.000000%.
- ########## Equal ##########
- ---------- eqst ----------
- min:       0.002805.
- max:       0.003014.
- mean:      0.002951.
- median:    0.002960.
- deviation: 0.006217.
- deviation: 0.000000%.
- ---------- eqml ----------
- min:       0.000152.
- max:       0.000158.
- mean:      0.000155.
- median:    0.000155.
- deviation: 0.001233.
- deviation: 0.000000%.
- ########## Total ##########
- ---------- eqst ----------
- min:       -0.000158.
- max:       0.147771.
- mean:      0.140922.
- median:    0.144310.
- deviation: 0.143125.
- deviation: 0.000202%.
- ---------- eqml ----------
- min:       -0.000009.
- max:       0.000003.
- mean:      -0.000003.
- median:    -0.000002.
- deviation: 0.001747.
- deviation: -0.000000%.

We run 2 benchmarks. Firsty, we see time needed to test equal on 2 random
string. In only one case, we will compare 2 equivalent string (by value, not
physically). This case highlights the difference on eqst on time executation.

Indeed, eqst (from Stdlib) is fast when it compare 2 differents string and
leaves up at the first byte which differ. So, when 2 string are equal, it will
take the biggest time:

- ---------- eqst ----------
- min:       0.002770.
- max:       0.150592.

You can see the minimum time on benchmarks and maximum times on eqst on random
inputs. But the most important result is the standard
deviation
:

- ---------- eqst ----------
- deviation: 0.000206%.

Which shows than some values on this benchmark are spread out compared on common
behavior (see mean value). This is exactly this context where we can do a
timing attack.

Then, we do the same benchmark on eqml and see the deviation:

- ---------- eqml ----------
- deviation: 0.000000%.

We launch then an other benchmark but on equal string and see, again, results.
In any case, we should have a standard deviation close to 0 %. Finally, compare
different string or equivalent string should take the same time. So a diff
betweem the first benchmark (different string) and the second (equivalent
string) should get a serie of 0 (or something close). We get same results and
see again standard deviation.

At the final step, we expect than standard deviation of eqml must be close to
0 %. If it's true, that means eqml takes the same time to compare any string
(if it's equal or not). Otherwise, we return an error.

Obviously, the final goal is to provide this kind of equal function so, of
course, tests works.

Happy hacking!

Install
Published
16 Oct 2018
Sources
eqaf-v0.2.tbz
md5=0832ef11a70fe5fe0c786fcf2a2a67cb
Dependencies
base-bytes
with-test
fmt
with-test
ocaml
>= "4.03.0"
Reverse Dependencies