rp2: Switch all RNG sources from ROSC to pico_rand. - #18834

Code size report:

Reference:  shared/readline: Handle \r and \n correctly as a newline. [a8b7155]
Comparison: rp2: Switch all RNG sources from ROSC to pico_rand. [merge of af772ff]
  mpy-cross:    +0 +0.000% 
   bare-arm:    +0 +0.000% 
minimal x86:    +0 +0.000% 
   unix x64:    +0 +0.000% standard
      stm32:    +0 +0.000% PYBV10
      esp32:    +0 +0.000% ESP32_GENERIC
     mimxrt:    +0 +0.000% TEENSY40
        rp2: +1136 +0.124% RPI_PICO_W[incl +8(bss)]
       samd:    +0 +0.000% ADAFRUIT_ITSYBITSY_M4_EXPRESS
  qemu rv32:    +0 +0.000% VIRT_RV32

Could you share your benchmark script?

This also needs tests --- not full NIST SP 800-22 or anything, but just basic coverage. (Preferably as part of a separate commit rebased to put it before your change in this PR's commit history.)

A test script like this would suffice:

# tests/extmod/os_urandom.py
try:
    import os
    os.urandom
except (ImportError, AttributeError):
    print("SKIP")
    raise SystemExit

for sz in (0, 1, 7, 8, 9, 1000):
    buf1 = os.urandom(sz)
    buf2 = os.urandom(sz)
    print(buf1 != buf2, len(buf))

Sure, here is my bechmark script:

import os
import time

def benchmark_urandom(size, iterations=1000):
    start = time.ticks_ms()
    for _ in range(iterations):
        os.urandom(size)
    elapsed = time.ticks_diff(time.ticks_ms(), start) / 1000
    bytes_total = size * iterations
    print(f"Size: {size:>4}B | {iterations} calls | {elapsed:.3f}s | {bytes_total/elapsed/1024:.2f} KB/s")

print("os.urandom benchmark")
print("-" * 55)

for size in [1, 4, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192]:
    benchmark_urandom(size)

print("-" * 55)

As for the test script, I would rather add a more complete test than that simple comparison.

As for the test script, I would rather add a more complete test than that simple comparison.

I understand the desire, but that's not the testing strategy this project uses! Anything that can be tested as a 1:1 comparison to CPython, should be tested that way --- even if that means writing two separate test files, a os_urandom0.py that tests the basic 1:1 stuff, and then a second os_urandom.py that uses a more complicated pass/fail test modality.

We also do not need to add another test that takes dozens of seconds to run, would risk timing out, and would need to be added as another special case to all of the test scripts, the way that comprehensive NIST SP 800-22 testing would be. The random functions in question are already fully tested as part of the pico-sdk's own test suite; the only thing that the tests here need to be able to reject are integration errors (i.e. "you called the function wrong" errors).

I think that there are some statistical test that are cheap and would still make sense. Those could detect issues in custom random implementations. The tests I would add:

1. Length test: len(os.urandom(n)) == n
2. Uniqueness test: os.urandom(n) != os.urandom(n)
3. Bit balance:

    n_bits = len(data) * 8
    ones = sum(bin(b).count("1") for b in data)
    z = abs(ones - n_bits / 2) / math.sqrt(n_bits / 4)
    return z < sigma_max

4. Byte frequency:

    counts = [0] * 256
    for b in data:
        counts[b] += 1
    n = len(data)
    expected = n / 256
    sd = math.sqrt(expected * (255 / 256))
    return all(abs(c - expected) <= sigma_max * sd for c in counts)

5. Serial correlation:

    n = len(data)
    mean = sum(data) / n
    var = sum((b - mean) ** 2 for b in data) / n
    if var == 0:
        return False
    cov = sum((data[i] - mean) * (data[i + 1] - mean) for i in range(n - 1)) / (n - 1)
    return abs(cov / var) < r_max

Thanks for submitting this, @mimi89999. I wanted to flag something else for discussion here, from the code size report:

    rp2: +1196 +0.130% RPI_PICO_W[incl +12(bss)]

This is a fairly substantial code size increase, so we need to look at the trade-off versus additional functionality benefits. Is the benefit purely that this generates random numbers faster, or is there a justifiable concern about the quality of rosc_random_u8() output?

(One other thought, all rp2 boards have mbedTLS enabled and rosc_random_u8() is already linked in as the entropy source, so it may be possible to use the mbedTLS random number generator without as much code size impact. I'm unsure if that meets the goals of this PR though, as the base entropy source is still rosc_random_u8().)

is there a justifiable concern about the quality of rosc_random_u8() output?

I just found the related issue #18831 (please link these when opening PRs!)

Based on the quote from the datasheet it does seem reasonable to switch implementations.

Why would the increased code size be an issue? This PR is changing only 5 lines. All the rest comes from the Pico SDK that is already included as a submodule. The impact on the binary size should be minimal.

Why would the increased code size be an issue? This PR is changing only 5 lines. All the rest comes from the Pico SDK that is already included as a submodule. The impact on the binary size should be minimal.

Apologies, by code size here we mean binary size (that's what the report comment shows).

+1K is not impossibly large but it's not nothing, we often spend time worrying about +100 byte changes. The question is always about the trade-off of size versus functionality.

MicroPython remains viable by constantly keeping an eye on these kind of small increases, otherwise they add up! (See contribution guidelines for more explanation.)

I understand the general concern about binary size, but this change only affects rp2 boards, which have plenty of flash. Also, pico_rand is an officially supported and maintained part of the Pico SDK, so I think the size trade-off is reasonable on this platform.

Is the benefit purely that this generates random numbers faster, or is there a justifiable concern about the quality of rosc_random_u8() output?

That needs to be judged against what kinds of uses we want to support, and how rigorously we want to take CPython's charge that the outputs be "suitable for cryptographic use". But points either way:

As noted in 6f06dca, @robert-hh did test it against several relevant statistical test suites. It attestedly does manage to whiten the underlying entropy enough that a general-purpose randomness test can't distinguish it from true random. And I'm definitely not someone who's studied the physics of ring oscillators deeply enough to actually find a break myself ---, so it's would be a bit disingenuous for me to assert that it's definitely not secure.

On the other hand, the current 8-bit LFSR isn't even one I'm able to find the name of --- it's not one of the canonical LFSR polynomials that you find everywhere that discusses how to do LFSRs.

What it also isn't, is one of the six conditioning algorithms endorsed by NIST SP 800-90B, 3.1.5.1.1, List of Vetted Conditioning Components; nor is it one of the DRBGs in NIST SP 800-90A. If there's another relevant standard I didn't check that includes it, I'd be happy to accept it, but there's also no comment I can find in the source code or commit history citing a specific source for this algorithm (as ought to be considered mandatory for any cryptographic algorithm).

NIST SP 800-90B 3.1.5.2, Using Non-vetted Conditioning Components, endorses a formula for estimating a conservative-best-case output entropy from a conditioning component like this one, given a few parameters about its input size, output size, internal state size, and per-bit entropy of the underlying source. I've not gone through the process of characterizing the underlying entropy-per-bit (if someone wants to go through 6.2, Non-IID Track: Entropy Estimation for Non-IID Data, I'd genuinely be curious to know how good ROSC even is), but as far as I can tell, there are no values for the $h_{in}$ parameter that would actually lead to a different conclusion. That conclusion being, that as parameterized in the current os.urandom ($n_{in}=8$, $n_{out}=8$, $nw=8$), the entropy per bit output from this conditioning component is strictly worse than the entropy-per-bit of the underlying ring oscillator. This is also the case for rosc_random_u32 ($n_{in}=32$, $n_{out}=8$, $nw=8$).

I think that there are some statistical test that are cheap and would still make sense. Those could detect issues in custom random implementations.

Fair enough, that seems quite reasonable.

Thanks @AJMansfield for the extra context.

My concerns about code size were mostly from reading the original PR description, which only describes a performance improvement and doesn't mention that Raspberry Pi don't recommend using the ROSC as a random number source. In light of that extra info plus this context, I think +1100 bytes of binary size is justified.

I am still kinda curious about where exactly the code size increase here derives from, though --- whether it's all just code from pico/rand.c, or if there's some other dependency module that's pulled in due to the specific set of defines configured for it.

I am still kinda curious about where exactly the code size increase here derives from, though --- whether it's all just code from pico/rand.c, or if there's some other dependency module that's pulled in due to the specific set of defines configured for it.

Good question! It's a shame they don't provide a way to get at the raw entropy source only, because I feel like we'd get a better result (and less code size) feeding this into mbedTLS DRBG and then calling that from os.urandom(). But in the absence of another supported entropy API the pico_rand method seems like the best way, we surely don't want to be verifying our own custom implementation!

#18558 would be quite the useful tool here.

Please also change ports/rp2/mbedtls_port.c:41 to use the pico_rand API as the mbedTLS entropy source. After that, it should be safe to remove rosc_random_u8() from main.c and the other files which mention it.

The ROSC is also used in https://github.com/micropython/micropython/blob/master/ports/rp2/mpconfigport.h#L161 and https://github.com/micropython/micropython/blob/master/ports/rp2/lwip_inc/lwipopts.h#L12. I thought that it might be better to introduce the change gradually. Should I change the RNG source in all those places in one commit?

On the other hand, the current 8-bit LFSR isn't even one I'm able to find the name of --- it's not one of the canonical LFSR polynomials that you find everywhere that discusses how to do LFSRs.

Maybe it would be good to ask the original author about that?

Should I change the RNG source in all those places in one commit?

One commit.

Note that both files also have the line extern uint32_t rosc_random_u32(void); that should also be removed, in favor of extern-declaring the method you're replacing it with.

I will look into it tomorrow. Today I am travelling.

So I looked at the implementation of get_rand_32() and get_rand_64() in pcio_rand/rand.c. It uses the pseudo_rng xoroshiro128++ which is seeded from various sources at the first use, like the hardware TRNG for RP2350 or ROSC for RP2040 plus time, RAM hash, board ID. All of these initial states are XORed to get the RNG initial state, so at least applying many seeding methods makes not things worse.

xoroshiro128++ is definitely better than the simple LFSR I used, since it cannot be rolled back. And one of the init methods is the ROSC which is currently used by the RP2040 as random source. So yes, switching should be OK.

Rebased and merged in 158cbd6

OK, that means that PR #18833 has to be adapted accordingly.

OK, that means that PR #18833 has to be adapted accordingly.

Ah, sorry, yes! I thought yours was opened after this one, but it was immediately before it.

No problem, it is changed now.