scalib.postprocessing.rankestimation#
Estimation of the rank of a true key given likelihood of sub-keys.
Rank estimation estimates the rank of the full (e.g. 128-bit) key based on a score for each value of its (e.g 8-bit) sub-keys. The scores must be additive and positive, with lower score meaning lower rank (e.g. negative log-likelihoods).
The rank_accuracy function allows to specify the desired precision of the bound in bits. It is the high-level, and its usage is recommended over the lower-level rank_nbin function. That function gives direct, lower-level control to the core algorithm, allowing to specify the number of bins in the histograms (whereas rank_accuracy tunes this parameter automatically).
By default, the rank_accuracy function uses scaled histograms for convolution. Unlike the standard histogram approach, this method scales down the bins before each convolution by a factor chosen to prevent exceeding a predefined limit. After the convolution, the histogram is scaled back to restore its original magnitude. This ensures correct functionality by avoiding negative values due to f64 overflows. Additionally, two histograms are used — one for the lower bound and one for the upper bound — to mitigate rounding errors and maintain precision.
Examples
>>> from scalib.postprocessing import rank_accuracy
>>> import numpy as np
>>> # define the correct key
>>> key = np.random.randint(0,256,16)
>>> # Derive the score for each key byte
>>> scores = np.ones((16,256)) * 1E-5
>>> scores[np.arange(16),key] = 1
>>> # Compute the full key rank (correct key must have rank 1).
>>> (rmin,r,rmax) = rank_accuracy(-np.log(scores),key)
>>> assert r == 1
Reference#
Estimate the rank of the full keys based on scores based on histograms. |
|
Estimate the rank of the full keys based on scores based on histograms. |
Notes
The rank estimation algorithm is based on [1], with the following optimization: computation of histogram bins with higher score than the expected key is skipped, since it has no impact on the final rank.
References