Opened 3 years ago

Closed 3 years ago

#1746 closed defect (fixed)

Tunnel Build Message Bloom Filter Review

Reported by: zzz Owned by: zzz
Priority: minor Milestone: 0.9.24
Component: router/general Version: 0.9.23
Keywords: Cc: str4d
Parent Tickets: #1745


Spec at http://i2p-projekt.i2p/en/docs/spec/tunnel-creation (Hop Processing and Creation 1st paragraph) says to feed the 32-byte AES-256 reply key into a Bloom filter.

But actual impl in BuildMessageProcessor? uses the first 32 bytes of the encrypted record, i.e. before decryption. Been this way since the beginning of this build style, Feb. 2006.

We use a DecayingHashSet? for the "Bloom" filter with a decay of only 60 seconds.

What's the replay attack scenario here? Basic principle is that your Bloom filter time has to exceed the valid timestamp time. But timestamp in build record is 1-hour resolution, so we need to extend the DHS time to one hour.

Analyze memory usage for 2 * 1 hour of DHS or switch to DBF if better.


Change History (8)

comment:1 Changed 3 years ago by zzz

  • Cc str4d added
  • Owner set to zzz
  • Parent Tickets set to 1745
  • Status changed from new to accepted

2 * 60s filter is useless because tunnel ID would be a dup. Attack would be to resend after 11 minutes.

Need new DHS or DBF that rotates at the top of the hour.

Actually seeing tunnel.buildRequestDup events in stats, average 1.2/hour, so this could be cause of #1745, but with bloom filter at 60 seconds seems like a lot. Bug somewhere? DHS hashes from 32 bytes down to 8, so may as well just use 8 bytes to start with. Could be just random collisions but again, sounds like a lot for a 60 second filter.

Again, is pre-decrypt filtering sufficient or not?

Need to fix the code or fix the docs. Need to enhance the docs in any case. Recommended filter time, etc.

comment:2 Changed 3 years ago by zzz

Implemented changes to switch to 60 minutes, switch from DHS to DBF, and use reply key instead of the first part of the encrypted data.

Still triggering bloom filter, investigating further, seeing reply keys of all zeros which is tripping the filter, but also reply keys that look decidedly nonrandom (long runs of zeros, duplicated data). Could be i2pd as we've had other all-zero issues from it. Investigating futher.

<zzz> re: PRNG, I'm working on our ticket 1746. Not quite ready to blame c++ routers yet but getting closer. Maybe PRNG, maybe elsewhere
<zzz> just as an example: reply key: [SessionKey: AAAAAAAAAACQAAAAAAAAAEQAAAAAAAAAoI8BJGF~AAA=]
<zzz> that should be a random number
<zzz> base 64, AAAAA is ofc all zeros
<zzz> reply key: [SessionKey: CAAAACAcuakAAAAAYL9ctwAAAAAIAAAAAFfWqQAAAAA=]
<zzz> [SessionKey: T0mkGLn6urQQAAAAAAAAAOD2ImCOfwAA0Oyrho5~AAA=]

<zzz> I started hexdumping the keys, here's an odd one
<zzz> 00000000  51 00 00 00 00 00 00 00  40 28 00 8c 36 7f 00 00  |Q.......@(..6...|
<zzz> 00000010  60 6b 03 8c 36 7f 00 00  ff ff ff ff 36 7f 00 00  |`k..6.......6...|
<zzz> and
<zzz> 00000000  51 00 00 00 00 00 00 00  b8 00 00 30 c5 7f 00 00  |Q..........0....|
<zzz> 00000010  a0 4d 7d 30 c5 7f 00 00  30 bb a6 5c c5 7f 00 00  |.M}0....0..\....|
<zzz> and
<zzz> 00000000  51 00 00 00 00 00 00 00  a0 d9 03 24 61 7f 00 00  |Q..........$a...|
<zzz> 00000010  d0 42 00 24 61 7f 00 00  40 0d 02 24 61 7f 00 00  |.B.$a...@..$a...|

note repeated data, including 7f 00 00

comment:3 Changed 3 years ago by zzz

'm logging previous hop, which would be c++ 1 of 6 times if it's a c++ problem
one chance in 6 you're first hop in a OB tunnel, assuming 3 hops
so far i've logged 7 routers and one is c++
or, more correctly, 1 chance in 4 if a participant; zero chance if a OBEP or IBGW

I'm going to check for all zeros and just drop it there (i.e. don't put it in the Bloom filter, so even the first one is rejected).

Can't say for sure it's coming from c++ routers, and may not be possible to be sure. Continuing to look for causes on the Java side. But it's time get i2pd and kovri involved. Repeating patterns or all zeros in an encryption key is an extremely serious issue.

I've seen 10 all-zeros keys in an hour of uptime. Example:

01-10 19:05:12.755 WARN [dHandler 1/1] r.tunnel.BuildMessageProcessor?: 4023381481: Bad reply key: BRR IBGW in: 1703263991 out 4070164923 to: [Hash: Ns5N5Sb5681z93bojAd8-OxMdxeqD2ixvmY8rzWqrIs=] layer key: [SessionKey: 2XVhvQ17cg~w4Rp~lIIUa~O9BEk00mGfO5BxEvkFpUo=] IV key: [SessionKey: RI2um5co5uJqKD8xMxMXRK1AU8kuF2ACJrHRBhVszvc=] reply key: [SessionKey: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA=] reply IV: sXZk-0KRjRwkbn5NpsLCxQ== hour: Sun Jan 10 18:00:00 GMT 2016 reply msg id: 673416717

comment:4 Changed 3 years ago by zzz

zzz> the way we do it in java, the reply key is 32 bytes straight out of the PRNG, done and done. I haven't found any opportunities for corruption yet.
<zzz> the layer key, IV key, and IV are also straight from the PRNG, but I've never seen them have strange values

comment:5 Changed 3 years ago by zzz

It appears that in i2pd/kovri TunnelConfig?.h, the reply key is never set and thus is leaking raw memory. Ditto the padding. The patterns in comment 2 above are perhaps addresses or other raw data. If true, this is a big problem and the codebase should be reviewed for similar issues. Shouldn't ever send uninitialized memory out on the wire. The comment " TODO: fill padding" is revealing.

comment:6 Changed 3 years ago by zzz

  • Milestone changed from undecided to 0.9.24

confirmed by anonimal to be a i2pd/kovri problem. I'll be cleaning up my changes described in comments 2 and 3, and pushing them soon for 0.9.24. All-zeros keys will be dropped.

comment:7 Changed 3 years ago by orignal

I agree that replyKey initilazation is missing due typo.
Will be fixed in i2pd shortly.

comment:8 Changed 3 years ago by zzz

  • Resolution set to fixed
  • Status changed from accepted to closed

In e46b7f38a7a7f3712a81a4008bfc8ad8126cb318 0.9.23-22

Note: See TracTickets for help on using tickets.