Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[kmac] Improve PRNG implementation #20828

Closed
msfschaffner opened this issue Jan 13, 2024 · 6 comments · Fixed by #21624
Closed

[kmac] Improve PRNG implementation #20828

msfschaffner opened this issue Jan 13, 2024 · 6 comments · Fixed by #21624
Assignees
Labels

Comments

@msfschaffner
Copy link
Contributor

msfschaffner commented Jan 13, 2024

Description

This is a sibling issue to #19091.
A similar PRNG improvement for KMAC should be evaluated.

@vogelpi
Copy link
Contributor

vogelpi commented Jan 19, 2024

Thanks for filing the issue @msfschaffner . I am currently working on this. The task can be broken down into the following steps:

  • PROLEAD setup for KMAC, a bit more involved due to how KMAC is constructed (the file containing the masked SHA3 core and the PRNG is kmac.sv also containing the TL-UL interface which is not practical for evaluation. Instead we need a reduced design version containing just the processing engine + PRNG).
  • Evaluating current design with PROLEAD.
  • Replace PRNG implementation with Bivium/Trivium-based implementation and additional fixes.
  • FPGA experiments
  • DV integration

@vogelpi
Copy link
Contributor

vogelpi commented Feb 19, 2024

Update: I've done the switch of the PRNG implementation and also the DV integration is mostly done. The FPGA evaluation is tricky and ongoing.

@vogelpi
Copy link
Contributor

vogelpi commented Feb 19, 2024

I've now updated the total effort to also include the DV / full security verification effort.

@vogelpi
Copy link
Contributor

vogelpi commented Feb 20, 2024

Update, I've also investigated the area and timing impact of the change using the Yosys + nangate45 synthesis flow. The situation is as follows:

Baseline Reworked core + Buffer Reworked core + Buffer + Bivium Reworked core + Buffer + Trivium
area 180 kGE 187 kGE 190 kGE 200 kGE
critical path 1.62 ns - 2.13 ns 2.08 ns
max clock freq 617 MHz - 469 MHz 480 MHz

The bottom line is that the critical path increases and is now inside the PRNG itself (because it's heavily unrolled - we generate 800 bits per clock cycle) but it's still very far away from the critical path of other IP cores and the whole chip. From an area perspective, Bivium would be 10 kGE smaller than Trivium. But since KMAC processes sensitive key material for keymgr we should probably go for Trivium to be on the safe side.

From a SCA perspective, PROLEAD suggests that anything with the reworked core and the added buffer stage is slightly better than the baseline but there are no big differences. I am now working on the the FPGA experiments.

vogelpi added a commit to vogelpi/opentitan that referenced this issue Feb 22, 2024
This commit switches the LFSR-based PRNG with an unrolled, Trivium-based
PRNG implementation to avoid brute-forcing attacks on the LFSR states.

The overall PRNG state decreases from 800 bits to 288 bits but due
to the heavy unrolling, the primitive can still generate 800 bits per
cycle as required by the masked SHA3 core.

This resolves lowRISC#20828.

Signed-off-by: Pirmin Vogel <[email protected]>
@vogelpi
Copy link
Contributor

vogelpi commented Feb 22, 2024

The DV work is now done and I also got the FPGA results for SHA3. It looks fantastic from an SCA perspective. KMAC mode experiments are currently running and I'll feed back once I have those results. The PR to integrate Trivium is here: #21624

@johngt the work for this is now done. I'll guess it will take some time for people to read through the PR and digest it. I'll answer questions of course but my main focus is now on other pressing issues FYI.

vogelpi added a commit to vogelpi/opentitan that referenced this issue Feb 22, 2024
This commit switches the LFSR-based PRNG with an unrolled, Trivium-based
PRNG implementation to avoid brute-forcing attacks on the LFSR states.

The overall PRNG state decreases from 800 bits to 288 bits but due
to the heavy unrolling, the primitive can still generate 800 bits per
cycle as required by the masked SHA3 core.

This resolves lowRISC#20828.

Signed-off-by: Pirmin Vogel <[email protected]>
vogelpi added a commit to vogelpi/opentitan that referenced this issue Feb 22, 2024
This commit switches the LFSR-based PRNG with an unrolled, Trivium-based
PRNG implementation to avoid brute-forcing attacks on the LFSR states.

The overall PRNG state decreases from 800 bits to 288 bits but due
to the heavy unrolling, the primitive can still generate 800 bits per
cycle as required by the masked SHA3 core.

This resolves lowRISC#20828.

Signed-off-by: Pirmin Vogel <[email protected]>
vogelpi added a commit to vogelpi/opentitan that referenced this issue Feb 22, 2024
This commit switches the LFSR-based PRNG with an unrolled, Trivium-based
PRNG implementation to avoid brute-forcing attacks on the LFSR states.

The overall PRNG state decreases from 800 bits to 288 bits but due
to the heavy unrolling, the primitive can still generate 800 bits per
cycle as required by the masked SHA3 core.

This resolves lowRISC#20828.

Signed-off-by: Pirmin Vogel <[email protected]>
vogelpi added a commit that referenced this issue Feb 29, 2024
This commit switches the LFSR-based PRNG with an unrolled, Trivium-based
PRNG implementation to avoid brute-forcing attacks on the LFSR states.

The overall PRNG state decreases from 800 bits to 288 bits but due
to the heavy unrolling, the primitive can still generate 800 bits per
cycle as required by the masked SHA3 core.

This resolves #20828.

Signed-off-by: Pirmin Vogel <[email protected]>
@vogelpi
Copy link
Contributor

vogelpi commented Apr 2, 2024

Update: As part of #22025 , we've switched to the Bivium implementation in #22021. All SCA experiments (including FPGA TVLA for SHA3 and KMAC) were repeated without the results changing notably.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants