Overflow Checking from 10.4 onwards

[pmcgee 23]

I have been learning about RSA encryption/decryption, so I started getting to know the (Rudy Velthuis') BigNumbers project, via GetIt and D12.3.

I started running into frustrating overflow errors (EIntOverflow) as soon as I started generating large prime numbers and doing some arithmetic with them.

 

I ended up trying the original Github repo (https://github.com/rvelthuis/DelphiBigNumbers) and using 10.3.3, and it worked fine.
Since then I spent quite some time to pull apart a simple line like: 

const                                                                                                 C
  CMultiplier = UInt64(6364136223846793005);                      
  CIncrement  = UInt64(1442695040888963407);                      

begin                                                              
{$IFOPT Q+}                                                          
{$DEFINE HasRangeChecks}                                           
{$ENDIF}
  FSeed := Int64(FSeed * CMultiplier + CIncrement);   // << EIntOverflow
  Result:= UInt32(FSeed shr (64 - Bits)); // Use the highest bits; Lower bits have lower period.
{$IFDEF HasRangeChecks}
{$RANGECHECKS ON}
{$ENDIF}
end;

Eventually, as a diagnostic adventure, I turned the one line into a soup of smaller steps to avoid overflow, and it works:

//  (A.e32 + B) * (C.e32 + D) = AC.e64 + (AD+BC).e32 + BD          
                                                                   
  A     :=       FSeed shr 32;          // top 32 bits             
  C     := CMultiplier shr 32;
  B     :=       FSeed and $ffffffff;   // bottom 32 bits
  D     := CMultiplier and $ffffffff;
  BD    := B*D;
  ADBC  := A*D+B*C;

//F     := ( (ADBC shl 32) + BD + CIncrement );
  f1    := BD + CIncrement;
  f2    := ADBC shl 32;
  F     := (f1 and $0fffffffffffffff) + (f2 and $0fffffffffffffff);

  FSeed := Int64(F);
//FSeed := Int64(FSeed * CMultiplier + CIncrement);

(This is inaccurate on the single most significant bit, but the algorithm says it's only using 48 bits, and has tested correctly so far)

 

I haven't tried 10.4.2, but 11.3 and 12.3 both give the overflow error.  Is this issue known to anyone? 

 

 

 

Edited 20 hours ago by pmcgee

[Kas Ob. 129]

9 hours ago, pmcgee said:

I haven't tried 10.4.2, but 11.3 and 12.3 both give the overflow error.  Is this issue known to anyone? 

I don't have any of the mentioned above IDEs, but i see a problem or two .. well more than that a lot, but will talk about your exact problem first

 

1) The directives are wrong and mixed, and here how they should look like

function TRandom.Next(Bits: Integer): UInt32;
begin
{$IFOPT R+}
{$DEFINE HasRangeChecks}
{$ENDIF}
{$IFOPT Q+}
{$DEFINE HasOverflowChecks}
{$ENDIF}
{$RANGECHECKS OFF}
{$OVERFLOWCHECKS OFF}
  FSeed := (FSeed * CMultiplier + CIncrement);
  Result := UInt32(FSeed shr (64 - Bits)); // Use the highest bits; Lower bits have lower period.
{$IFDEF HasRangeChecks}
{$RANGECHECKS ON}
{$ENDIF}
{$IFDEF HasOverflowChecks}
{$OVERFLOWCHECKS ON}
{$ENDIF}
end;

Because we have two overflow check can be triggered here, not one !, Integer overflow range overflow come from multiplication and form truncation while mixing signed and unsigned, both need to be disabled, also the R+ for the range while wrongly was Q.

 

2) I tried this small test

procedure RunTest;
var
  Rand: IRandom;
  A, B, C: BigInteger;
begin
  Rand := TRandom.Create($FF00FE01FD02FC03);     // sooner ! Trigger overflow check at TRandomBase.NextBytes
  //Rand := TRandom.Create($FF00FF01FF02FF03);     // Trigger overflow check at TRandom.Next

  A.Create(1024, Rand);
  B.Create(1024, Rand);

  C := A * C;

  Writeln('A = ' + A.ToHexString);
  Writeln('B = ' + B.ToHexString);
  Writeln('C = ' + C.ToHexString);
end;

And we have another place that has an overflow, but the fix is easy (again sign bit!!) 

procedure TRandomBase.NextBytes(var Bytes: array of Byte);
var
  Head, Tail: Integer;
  N, {Rnd,} I: Integer;
  Rnd : UInt32;          //  <--- fix overflow
begin

Didn't go through more tests or any deeper in digging into the source.

 

Now to the other problems

3) This pseudorandom number generator is not cryptographically secure , it has very small duration and depend on single modular operation which is 2^(64-Bits)= 2^k, this can't be considered secure it is as predictable as it can be by design, but choosing 2^k make brute force algorithm for it way much faster !

4) I don't understand from where the assumption of only 48 bits are only used, this is strange and out of the context or this family of PRNG, may be i missed something with Bits, but will not dig deeper in it.

5) the core problem is depending on Int64, this is signed and by using signed we lose a bit and confuse the compiler and math, while gains nothing in return, this family of PRNG which call LCG https://en.wikipedia.org/wiki/Linear_congruential_generator doesn't handle signed numbers, and doesn't need as it is by definition, so using Int64 should be replaced with UInt64 for the constants, and the algorithm too.

6) tried to figure out this code 

10 hours ago, pmcgee said:

 

//  (A.e32 + B) * (C.e32 + D) = AC.e64 + (AD+BC).e32 + BD          
                                                                   
  A     :=       FSeed shr 32;          // top 32 bits             
  C     := CMultiplier shr 32;
  B     :=       FSeed and $ffffffff;   // bottom 32 bits
  D     := CMultiplier and $ffffffff;
  BD    := B*D;
  ADBC  := A*D+B*C;

//F     := ( (ADBC shl 32) + BD + CIncrement );
  f1    := BD + CIncrement;
  f2    := ADBC shl 32;
  F     := (f1 and $0fffffffffffffff) + (f2 and $0fffffffffffffff);

  FSeed := Int64(F);
//FSeed := Int64(FSeed * CMultiplier + CIncrement);

 

You are going with Karatsuba https://en.wikipedia.org/wiki/Karatsuba_algorithm , nice it is the right way when you are in the corner, also much cleaner for limbs, yet the last masking is again wrong assuming (you are following the original code) it can or should be signed operation, this should be changed to unsigned, and return the sign bit to the fold, as it is by design is using the highest 32 bit, by losing the sign, where entropy is lost, we left with 31 bit randomness.

 

About learning and implementing RSA, yes do it and you will learn much, and i wish you good luck,

 

also a suggestion : why not read more about CSPRNG and implement one ,a cryptographically secure (CS) one, there is one i liked very much due it speed and portability, it is based on CHAHCA with reduced rounds called ChaCha8, it use the same permutation as ChaCha20 but with 8 rounds, it is secure and small as it can be, and used in Go Lang applications extensively,

anyway it is not so important and most important thing is understanding is that security is like a chain and the chain is weak as its weakest link, randomness is always the most crucial link that when break (insecure) it will render everything built on it insecure, and last suggestion if you are going to use you own implementation of RSA in production for clients then test it then test it and test it again and think a lot before using your own implementation, it is not recommended by anyone ( as i think you read again and again, things like don't implement your own...), but you should learn it inside out, so go with it. 

[pmcgee 23]

17 hours ago, pmcgee said:

 

{$IFOPT Q+}                                                          
{$DEFINE HasRangeChecks}                                           
{$ENDIF}

{$IFDEF HasRangeChecks}
{$RANGECHECKS ON}
{$ENDIF}

 

Thanks for your reply. 

These directives are just quoted as-is from the library on GitHub (uptodate and original) and GetIt.

 

I haven't pulled back to get the higher level view here, having been stuck in tracing through the code to nail down the issues.

 

FSeed is declared as Int64.  

The function here is : function TRandom.Next(Bits: Integer): UInt32; 

And the call is : Rnd := Next(32); 

where Rnd is declared as Integer;

 

I have checked that the actual bits (of course, I guess) stay the same ... but this seemingly cavalier application of (kinda) hidden casting has caused me to squint a little. 🤨 

 

Edit : 

Incorporating the corrected compiler directives, sanity is returned and FSeed can be calculated in one line again. 🎉

 

In procedure TRandomBase64.NextBytes(var Bytes: array of Byte);  Rnd is declared as UInt64.

With the above change, there is a Range Check Error on assigning Rnd (in TRandom.NextBytes)
I think it is clear that Rnd should be declared as UInt32.

 

Aaaaannnnd, on reading further down your response, I see you already concluded the same. 😅

Edited 3 hours ago by pmcgee

[pmcgee 23]

Quote

6) tried to figure out this code ... You are going with Karatsuba 

No, I don't think so. I was just doing the multiplication in pieces that didn't overflow 64 bits.
I was just taking a multiplication of two 64-bit numbers, and thinking of it kinda like a long multiplication from school.

 

If we consider each number in their two halves (upper and lower 32 bits), then when we only want to keep the bottom 64-bits, we can throw away part of the multiplications ...

and do some of the multiplication in the lower part of the range before shifting it back up again.

 

Quote

yet the last masking is again wrong assuming

Yes. I was going to be potentially incorrect in the 64th bit, but it was easy to do, and wasn't affecting the testing I had done to that stage.

 

 

 

Quote

About learning and implementing RSA, yes do it and you will learn much, and i wish you good luck.
... if you are going to use you own implementation of RSA in production for clients ...

No, not at all.  I have been, with friends, going through Alexander Stepanov's book (and related videos) "From Mathematics to Generic Programming", and he describes RSA in there.

We set ourselves the task to implement it in different languages.

Its pretty remarkable how simple the mechanical parts are (in concept).

 

Edited 2 hours ago by pmcgee