View Issue Details

IDProjectCategoryView StatusLast Update
0006148Talerexchangepublic2020-04-02 14:07
ReporterfefeAssigned ToChristian Grothoff 
Status resolvedResolutionfixed 
Product Version0.7.0 
Target Version0.7.1Fixed in Version0.7.1 
Summary0006148: TALER_amount_normalize is O(n) where O(1) would have sufficed
DescriptionTALER_amount_normalize takes an amount, which is a (64-bit value, 32-bit fractional part) tuple, and if the fractional part is > 100000000 it will reduce it and increase the value, checking for overflow.

However, instead of using the remainder of a division, it will do a loop that increments the value part by 1.

Theoretically an attacker could provide a value that causes the loop to run many times and waste CPU. Technically this is considered a denial of service attack.

Steps To Reproduce537 while ( (amount->value != UINT64_MAX) &&
538 (amount->fraction >= TALER_AMOUNT_FRAC_BASE) )
539 {
540 amount->fraction -= TALER_AMOUNT_FRAC_BASE;
541 amount->value++;
542 ret = GNUNET_OK;
543 }
544 if (amount->fraction >= TALER_AMOUNT_FRAC_BASE)
545 {
546 /* failed to normalize, adding up fractions caused
547 main value to overflow! */
548 invalidate (amount);
549 return GNUNET_SYSERR;
550 }

Note that we call invalidate on the amount, so we do not actually need the remaining fractional part.
We could just do

if (amount->fraction >= TALER_AMOUNT_FRAC_BASE) {
  uint32_t overflow = amount->fraction / TALER_AMOUT_FRAC_BASE;
  amount->fraction %= TALER_AMOUNT_FRAC_BASE;
  if ((amount->value += overflow) < overflow) {
    return GNUNET_SYSERR;
TagsNo tags attached.


Christian Grothoff

2020-04-02 14:06

manager   ~0015491

Last edited: 2020-04-02 14:07

View 2 revisions

DDoS "potential" -- well, except:
1) TALER_AMOUNT_FRAC_BASE is 100.000.000, and fractions are 32-bit values, so you'd get at most 40 iterations out of your DDoS loop. Compare the cost of division to subtraction and you may almost get nothing for your DDoS.
2) The function is internally _only_ used after arithmetic operations, where say adding up two fractions may have resulted in an overflow. But that overflow basically is limited to the FRAC_BASE (all values should always be normalized, so one of the few calls that do anything are in #TALER_amount_add/divides(). I'm not sure it is even possible for an attacker to supply a fraction exceeding the FRAC_BASE-value.

But, I take removing of an unnecessary loop as cosmetics.

That said, there is a 'real' bug in that function, in that it doesn't enforce the MAX_AMOUNT_VALUE limit. So I've added that.
It means that the arithmetic overflow check really can't _actually_ hit anymore, but I've kept it anyway as it's basically free.
Fixed in a039926b..e9de3374

Issue History

Date Modified Username Field Change
2020-04-02 12:59 fefe New Issue
2020-04-02 12:59 fefe Status new => assigned
2020-04-02 12:59 fefe Assigned To => Christian Grothoff
2020-04-02 14:06 Christian Grothoff Note Added: 0015491
2020-04-02 14:06 Christian Grothoff Fixed in Version => 0.7.1
2020-04-02 14:06 Christian Grothoff Target Version => 0.7.1
2020-04-02 14:06 Christian Grothoff Status assigned => resolved
2020-04-02 14:06 Christian Grothoff Resolution open => fixed
2020-04-02 14:07 Christian Grothoff Note Edited: 0015491 View Revisions