Learning record of Dilithium

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 1.4k 阅读时长 ≈ 1 分钟

Dilithium

paper 义眼顶真 读后感
https://pq-crystals.org/dilithium/data/dilithium-specification-round3-20210208.pdf, [BDK+] NIST implement document.
[DKL+18] similar to doc above.
MUTS22 when \(y_{i, j}\) is zero.
[RJH+18] only s_1 can also sign
Lyubashevsky Fiat-Shamir with Aborts framework
DDLL13 BLISS signature scheme
https://eprint.iacr.org/2023/1891 CPA-PoI on NTT

MUTS22

recovering \(s_1\) based on Multi-Layer Perceptron (MLP) machine-learning, and according to a [RJH+18], it's possible to sign using just that knowledge. the leaking point is bit-unpacking function when generating the vector y (input \(\rho^{'}\) in XOF to generate a byte string and unpacked it into \(\ell\) polynomials, who has N cocoefficients). the function use in [BDK+]:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
void polyz_unpack(poly *r, const uint8_t *a) {
  unsigned int i;
  DBENCH_START();

#if GAMMA1 == (1 << 17)
  for(i = 0; i < N/4; ++i) {
    r->coeffs[4*i+0]  = a[9*i+0];
    r->coeffs[4*i+0] |= (uint32_t)a[9*i+1] << 8;
    r->coeffs[4*i+0] |= (uint32_t)a[9*i+2] << 16;
    r->coeffs[4*i+0] &= 0x3FFFF;

    r->coeffs[4*i+1]  = a[9*i+2] >> 2;
    r->coeffs[4*i+1] |= (uint32_t)a[9*i+3] << 6;
    r->coeffs[4*i+1] |= (uint32_t)a[9*i+4] << 14;
    r->coeffs[4*i+1] &= 0x3FFFF;

    r->coeffs[4*i+2]  = a[9*i+4] >> 4;
    r->coeffs[4*i+2] |= (uint32_t)a[9*i+5] << 4;
    r->coeffs[4*i+2] |= (uint32_t)a[9*i+6] << 12;
    r->coeffs[4*i+2] &= 0x3FFFF;

    r->coeffs[4*i+3]  = a[9*i+6] >> 6;
    r->coeffs[4*i+3] |= (uint32_t)a[9*i+7] << 2;
    r->coeffs[4*i+3] |= (uint32_t)a[9*i+8] << 10;
    r->coeffs[4*i+3] &= 0x3FFFF;

    r->coeffs[4*i+0] = GAMMA1 - r->coeffs[4*i+0];
    r->coeffs[4*i+1] = GAMMA1 - r->coeffs[4*i+1];
    r->coeffs[4*i+2] = GAMMA1 - r->coeffs[4*i+2];
    r->coeffs[4*i+3] = GAMMA1 - r->coeffs[4*i+3];
  }
#elif GAMMA1 == (1 << 19)
  for(i = 0; i < N/2; ++i) {
    r->coeffs[2*i+0]  = a[5*i+0];
    r->coeffs[2*i+0] |= (uint32_t)a[5*i+1] << 8;
    r->coeffs[2*i+0] |= (uint32_t)a[5*i+2] << 16;
    r->coeffs[2*i+0] &= 0xFFFFF;

    r->coeffs[2*i+1]  = a[5*i+2] >> 4;
    r->coeffs[2*i+1] |= (uint32_t)a[5*i+3] << 4;
    r->coeffs[2*i+1] |= (uint32_t)a[5*i+4] << 12;
    r->coeffs[2*i+0] &= 0xFFFFF;

    r->coeffs[2*i+0] = GAMMA1 - r->coeffs[2*i+0];
    r->coeffs[2*i+1] = GAMMA1 - r->coeffs[2*i+1];
  }
#endif

  DBENCH_STOP(*tpack);
}

two phases:

  1. profiling phase: execute signing process with random input messages on A device and collect the power usage during the execution of the bit-unpacking function. Training their classifiers with labelled traces of sensitive internal data.
  2. attack phase：By observing the power traces of the signature generation on Device B, predicting the sensitive internal data, using Least Squares Method(LSM) to get a solution candidate and uncovering the secret key \(s_1\) by solving an Integer Linear Program(ILP).

you cant distinguish the difference of an unpacking result between zero and none-zero, so they train machine-learning classifiers

(I indeed cant distinguish it)

image-20231116123634446

it is obvious that when \(y_{i, j}\) is zero one can recovery the secret \(s_1\), so authors use the ml tech to distinguish whether it's zero or none-zero. when this is done, thing's getting easy.