Re: Ternary Encoding :-)

Stefan Claas <pollux@tilde.club> wrote:

My old pads program is already updated.  It compiled flawlessly for
many different platforms, including macOS, but I do not know if they
all support TPM 2.0, like Windows and Linux does.
 
https://github.com/706f6c6c7578/pads

Looking over your pads program, while you are retreiving true random
numbers from the TPM chip, you are introducing a bias when you use the
random bytes from the TPM to output letters or digits.

Take for example your "letters" arm:

  if l {
    random, _ := tpm2.GetRandom(rwc, 5)
    for m := 0; m < 5; m++ {
      fmt.Printf("%c", 'A'+(random[m]%26))
    }
  }

Now, if I've decoded the awful documentation for the TPM2 module
properly [1] the tpm2.GetRandom call will return five bytes (presumably
unsigned bytes) of random data.

Then, you loop over the five bytes, outputting the letter that
corresponds to ASCII A plus the remainder after dividing the byte by
26.  Which is where you introduce a bias.

A byte will have a value from 0 to 255, for 256 total values.

But 26 does not evenly divide 256.  256/26 ~ 9.846

26 divides 256 evenly 9 times, no problem here.  That covers values 0
to 233.  But for any bytes returned from GetRandom that fall into the
range 234 to 255, you have only 21 possible values that can return from
the modulo.  So your remainder will be only 0 through 21.  You'll never
get 22 through 25 out, because there is not enough numeric range in the
"tail" to return 22 through 25 from the modulo.  So for any bytes with
values 234 to 255 from the TPM, you can return A through V but will
never return W, X, Y or Z.

So your resulting letters will have a bias for A through V.

The fix is easy, first check the value of the byte you are about to
use, and if it happens to be greater than 233, throw that byte away and
pull another from the TPM.

You produce the same bias for your digits, since an unsigned three byte
value is 2^24 = 16_777_216 but that is not evenly divisible by 100000. 
So you'll have a range of "low numbers" that are slightly more likely
to occur (a bias) than they should if they were truly random.

This is one of the many examples where it is very easy to mess up the
implementation of a crypto system such that a crack is left for a
skilled cryptographer to exploit.


[1] it is actually worse than awful, it is non-existant, but that seems
to be a normal given aspect for most of the 'newfangled' languages
out there, no documentation in sight anywhere