[Libre-soc-bugs] [Bug 1151] Ed25519 demo

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=1151

--- Comment #4 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #3)
> given that the probability of being wrong even when running just one
> single example is (2^128-1) / (2^128) for a 128-bit algorithm and
> (2^256-1) / (2^256) for a 256-bit one it is an absolute no-brainer
> to justify "success" on the basis of passing *even one* of the "known
> examples"
> provided by a c reference implementation.  run two well-known examples
> and that becomes a probability of (2^128-1)^2 / (2^128)^2

that assumes the crypto primitive was implemented correctly, the probability is
much higher than that that the primitive is wrong for only some inputs.

e.g. AES-128 uses at most 160 of the 256 S-box entries for any one encryption
(each round has 16 S-box accesses, there are 10 rounds), so, assuming those are
randomly distributed, for 2 AES-128 encryptions, only about 183 S-box entries
are ever accessed, so if you have one wrong, you have about a 72% percent
chance of detecting that.

my code:
import random
def count_accessed(c):
    sbox = [False] * 256
    for _ in range(c):
        sbox[random.randrange(256)] = True
    return sum(sbox)
def wrong_accessed(c, w):
    for _ in range(c):
        if random.randrange(256) < w:
            return True
    return False
# average number of S-box entries accessed for 2 encryptions:
c = 10000; print(sum(count_accessed(160*2) for _ in range(c)) / c)
# probability one wrong S-box entry will be accessed for 2 encryptions:
c = 10000; print(sum(wrong_accessed(160*2, 1) for _ in range(c)) / c)

-- 
You are receiving this mail because:
You are on the CC list for the bug.