View Issue Details
| ID | Project | Category | View Status | Date Submitted | Last Update |
|---|---|---|---|---|---|
| 0006148 | Taler | exchange | public | 2020-04-02 10:59 | 2021-09-02 16:14 |
| Reporter | fefe | Assigned To | Christian Grothoff | Resolution deadline | |
| Implementer | Reviewer | ||||
| Release signed by | Deployed by | ||||
| Verifier | Communicator | ||||
| Data protection authority notification required | No | ||||
| CSIRT notification required | No | ||||
| Estimated effort (hours) | Actual effort (hours) | 0 | |||
| Fast-track | No | ||||
| Work package | none | ||||
| Priority | normal | Severity | trivial | Reproducibility | N/A |
| Status | closed | Resolution | fixed | ||
| Product Version | 0.7.0 | ||||
| Target Version | 0.7.1 | Fixed in Version | 0.7.1 | ||
| Summary | 0006148: TALER_amount_normalize is O(n) where O(1) would have sufficed | ||||
| Description | TALER_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 Reproduce | 537 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) { invalidate(amount); return GNUNET_SYSERR; } } | ||||
| Tags | No tags attached. | ||||
| 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 | |
| Fix committed to master branch. | |
| Date Modified | Username | Field | Change |
|---|---|---|---|
| 2020-04-02 10:59 | fefe | New Issue | |
| 2020-04-02 10:59 | fefe | Status | new => assigned |
| 2020-04-02 10:59 | fefe | Assigned To | => Christian Grothoff |
| 2020-04-02 12:06 | Christian Grothoff | Note Added: 0015491 | |
| 2020-04-02 12:06 | Christian Grothoff | Fixed in Version | => 0.7.1 |
| 2020-04-02 12:06 | Christian Grothoff | Target Version | => 0.7.1 |
| 2020-04-02 12:06 | Christian Grothoff | Status | assigned => informing |
| 2020-04-02 12:06 | Christian Grothoff | Resolution | open => fixed |
| 2020-04-02 12:07 | Christian Grothoff | Note Edited: 0015491 | |
| 2021-08-24 14:23 | Christian Grothoff | Status | informing => closed |
| 2021-09-02 16:13 | Christian Grothoff | ||
| 2021-09-02 16:14 | Christian Grothoff | Note Added: 0018267 |