Usage of a weak PRNG could allow to recover the shared secret

[sylvainpelissier]

Issue
The function generateRandomShare is responsible for generating the random masking shares sent to other participants. In the current implementation, it calls tf.randomUniform, which in TensorFlow.js is backed by seedrandom.alea. It is a deterministic, non-cryptographic PRNG and is therefore not suitable for generating masks in a secure aggregation protocol.

If an attacker can observe enough generated values, they may be able to infer or narrow the internal state and predict other share values. The final share is not sampled from the same distribution as the others. Instead, it is computed as the residual needed to ensure that all shares sum to the secret. As a consequence, the final share has a different statistical distribution and can have a much larger magnitude than the randomly sampled shares, especially when the number of participants increases. This makes it distinguishable from the others and may weaken the privacy properties of the scheme. In particular, if an attacker can identify or obtain that last share and also recover the other shares, then reconstructing the secret becomes straightforward.

To Reproduce
The following code:

function main(): void {
  const num = 3
  const secureAggregator = new aggregator.SecureAggregator(100)

  for (let index = 0; index < num; index++) {
    secureAggregator.registerNode(`peer-${index + 1}`)
  }

  const secret = WeightsContainer.of(
    tf.tensor1d([0.12, -0.34, 0.56, -0.78]),
    tf.tensor2d([
      [0.01, -0.02],
      [0.03, -0.04],
      [0.05, -0.06],
    ]),
  )

  const shares = secureAggregator.generateAllShares(secret)
  const lastShare = shares.last()
  if (lastShare === undefined)
    throw new Error('no shares were generated')
  console.dir(toSerializable(lastShare), { depth: null })
}

main()

May produce the output:

Share 3:
[
  [
    -134.71546936035156,
    -34.92858123779297,
    127.90728759765625,
    -114.26385498046875
  ],
  [
    [ -134.82546997070312, -34.60858154296875 ],
    [ 127.37728881835938, -113.52385711669922 ],
    [ -25.76422882080078, -47.41002655029297 ]
  ]
]

With values outside of the range [-100,100] contrary to other shares.

Expected behavior
The random values used for share generation should be drawn directly from a cryptographically secure source such as crypto.getRandomValues, rather than from a seeded generic PRNG. Since crypto.getRandomValues already provides cryptographically secure randomness, there is no need to derive a seed and pass it into tf.randomUniform. If a seed-based generator is required for some reason, it should be a CSPRNG and seeded with a seed of at least 128 bits of entropy.

Additional context
Issue found together with @lucamul

[JulienVig]

Thanks for pointing this out! What I believe was the reference paper (Q. Li (2019), Privacy-preserving distributed average consensus based on additive secret sharing) indeed defines additive secret sharing differently from what was implemented, I don't know what was the motivation behind the current implementation.

So the concrete changes to implement are:

1. Sample $n-1$ integers (via crypto.getRandomValues) mod $p$, $p$ being a prime number, rather than using tf.randomUniform
2. compute $s_n$ as the remaining difference mod p

Does this address the issue soundly?

[sylvainpelissier]

Yes but in this case your secret is a float so you have to convert it to an integer modulo $p$ in a reversible manner. Then yes it works.