Re: Ternary Encoding :-)

On 2025-01-03 06:03, Rich wrote:

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.

Why waste 8.98% of random bytes, especially when generating large keys from slow source of randomness? Lumbroso's FastDiceRoller algorithm
consumes the exact number of bits needed to produce integer in requested range: https://arxiv.org/abs/1304.1916
Exhibit 1:
inline uint32_t FastDiceRoller(unsigned int n) {
   uint64_t v = 1, c = 0;
   while (true) {
     v = v << 1;
     c = (c << 1) + randombit;
     if (v >= n) {
       if (c < n) return c;
       else {
         v = v - n;
         c = c - n;
       }
     }
   }
}
Exhibit 2:
function FastDiceRoller(const n: longword): longword;
var
   v, c: Int64;
begin
   v := 1;
   c := 0;
   while (true) do
   begin
     v := (v shl 1);
     c := (c shl 1) + RandomBit;
     if (v >= n) then
     begin
       if (c < n) then
       begin
         result := LongWord(c);
         Exit;
       end
       else
       begin
         v := v - n;
         c := c - n;
       end;
     end;
   end;
end;
--
-----BEGIN PGP PUBLIC KEY FINGERPRINT-----
5745 807C 2B82 14D8 AB06 422C 8876 5DFC 2A51 778C
------END PGP PUBLIC KEY FINGERPRINT------