ReplayProtector.h 3.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106
  1. /* vim: set expandtab ts=4 sw=4: */
  2. /*
  3. * You may redistribute this program and/or modify it under the terms of
  4. * the GNU General Public License as published by the Free Software Foundation,
  5. * either version 3 of the License, or (at your option) any later version.
  6. *
  7. * This program is distributed in the hope that it will be useful,
  8. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  9. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  10. * GNU General Public License for more details.
  11. *
  12. * You should have received a copy of the GNU General Public License
  13. * along with this program. If not, see <http://www.gnu.org/licenses/>.
  14. */
  15. #ifndef ReplayProtector_H
  16. #define ReplayProtector_H
  17. #include "util/Bits.h"
  18. #include <stdbool.h>
  19. struct ReplayProtector
  20. {
  21. /** internal bitfield. */
  22. uint64_t bitfield;
  23. /** Internal offset. */
  24. uint32_t baseOffset;
  25. /** Number of definite duplicate packets. */
  26. uint32_t duplicates;
  27. /** Number of lost packets. */
  28. uint32_t lostPackets;
  29. /**
  30. * Number of packets which could not be verified because they were out of range.
  31. * Growing lostPackets and receivedOutOfRange together indicate severe packet
  32. * reordering issues.
  33. * receivedOutOfRange growing along indicates duplicate packets.
  34. */
  35. uint32_t receivedOutOfRange;
  36. };
  37. static inline int RelayProtector_lostInShift(uint64_t bitfield, int shiftAmount)
  38. {
  39. if (shiftAmount == 0) {
  40. return 0;
  41. }
  42. if (shiftAmount > 63) {
  43. return shiftAmount - Bits_popCountx64(bitfield);
  44. }
  45. return shiftAmount - Bits_popCountx64(bitfield << (64 - shiftAmount));
  46. }
  47. /**
  48. * Check a nonce and file it as being seen.
  49. * Don't call this until the packet has been authenticated or else forged packets will
  50. * make legit ones appear to be duplicates.
  51. *
  52. * @param nonce the number to check, this should be a counter nonce as numbers less than 32 minus
  53. * the highest seen nonce will be dropped erroniously.
  54. * @param context the context
  55. * @return true if the packet is provably not a replay, otherwise false.
  56. */
  57. static inline bool ReplayProtector_checkNonce(const uint32_t nonce, struct ReplayProtector* context)
  58. {
  59. if (nonce < context->baseOffset) {
  60. context->receivedOutOfRange++;
  61. return false;
  62. }
  63. uint32_t offset = nonce - context->baseOffset;
  64. while (offset > 63) {
  65. #define ReplayProtector_DO_SHIFT(bits) \
  66. context->baseOffset += (bits); \
  67. if ((bits) > 63) { \
  68. context->bitfield = 0; \
  69. } else { \
  70. context->bitfield >>= (bits); \
  71. } \
  72. offset -= (bits);
  73. if ((context->bitfield & 0xffffffffu) == 0xffffffffu) {
  74. // happy path, low 32 bits are checked in, rotate and continue.
  75. ReplayProtector_DO_SHIFT(32);
  76. } else {
  77. // we are going to have to accept some losses, take offset - 47 to mitigate that
  78. // as much as possible.
  79. context->lostPackets += RelayProtector_lostInShift(context->bitfield, offset - 47);
  80. ReplayProtector_DO_SHIFT(offset - 47);
  81. }
  82. }
  83. if (context->bitfield & (((uint64_t)1) << offset)) {
  84. context->duplicates++;
  85. return false;
  86. }
  87. context->bitfield |= (((uint64_t)1) << offset);
  88. return true;
  89. }
  90. #endif