the bloom filter mind virus claims another victim

11 5 178

brb engineering bloom filter collisions

1 31

(probably a non-issue but could be mitigated with a keyed/salted hash)

1 20

Tim 17 Dec 2024

david let people enjoy things

1 1 20

https://github.com/jasondavies/bloomfilter.js/blob/master/bloomfilter.js

I've actually audited this impl before because it was vendored into something else, never knew it was a popular library in its own right. I have several issues to report lol github.com/jasondavies/...

2 1 27

I already have code to generate the dual-fnv-1a collisions that would be required to disappear a post of my choice, assuming I can get my "tainted" post viewed first

2 24

const good = "https://bsky.app/profile/samuel.bsky.team/post/3ldjv73zdqk2g"; const evil = "https://bsky.app/profile/retr0.id/post/3ieuudbl4qj7d"; (fnv_1a(good) === fnv_1a(evil)) && (fnv_1a(good, 1576284489) === fnv_1a(evil, 1576284489)) (yeah I did http not at:// URIs because I was lazy lol)

2 13

GitHub Gist: instantly share code, notes, and snippets.

my script takes like 48GB of RAM iirc (or maybe it was just 24 I can't remember), but completes in under a minute gist.github.com/DavidBuchana...

fnv_crack_public.c

gist.github.com

1 10

now that I'm looking at this again with my current knowledge I'm pretty sure I could make it go way faster... I basically treat a||b as a 64-bit hash and do a meet-in-the-middle with a big LUT. but I think I could write a solver for one of the halves, then meet-in-the-middle on the other half,

1 8

giving 2^16 total work for the whole attack (as opposed to the 2^32 that it currently is)

mcyoung 🏳️‍🌈18 Dec 2024

omfg. people really be "im gonna roll my own fnv1 in javascript" when Crypto.subtle.digest("SHA-256", ...) is right there

2 4

Natanael, Tech janitor 18 Dec 2024

fnv1a is faster, and even if you use a cryptographically secure hash, finding collisions is still trivial for a fixed bloom filter size

2 3

The reason Mozilla's CRLite works is because the targets/matched entries are not open ended + it uses 3 layers of bloom filters in opposite directions (inclusion / exclusion / inclusion), so errors are strictly controlled Collision resistance is necessary for stuff like this

not to mention, this code was written before webcrypto apis existed

1 1

mcyoung 🏳️‍🌈18 Dec 2024

oh yes, there is also the bloom filter brain damage, I will grant that. alas, people do not seem to get how entropy works...

Limi Lumen 18 Dec 2024

I just wish Crypto.subtle had a bit wider choice of algorithms, "widely" used stuff like (X)ChaCha20(Poly1305) or BLAKE2(b) are missing even SHA-3 is missing. And I wonder if Kyber and Dilithium will ever be added even if they widely become adopted.

1 1

Limi Lumen 18 Dec 2024

To be fair (X)ChaCha20(Poly1305) and BLAKE2(b) are all reasonable safe+fast in WASM AFIK and it's probably more sustainable to make sure WASM has the right extensions to allow secure implementations of modern ciphers then adding a ton of crypto you need to maintain forever.

daniel holmgren 🫠17 Dec 2024

oh lol @dholms.xyz is already in the issues complaining about the fp rate - I know why that is

1 8

wait why is it 😆 @danabra.mov posted a screenshot of my issue from 4 years ago lol. can't remember the details of it lol

2 6

daniel holmgren 🫠17 Dec 2024

wait @martin.kleppmann.com fixed the FP issue?? github.com/jasondavies/... lmao small world

Fix excessively high rate of false positives (fixes #15) · jasondavies/bloomfilter.js@ed86edb

The problem was that the locations of the bloom filter bits for a particular entry were not independent pseudorandom values as they should be. In particular, if you have two strings that have a FNV...

Martin Kleppmann 18 Dec 2024

2 12

Ha! The false probability rate was much worse before my fix, but looks like I screwed up the fix. Basically nobody knows how to implement the "k independent hash functions" bit of Bloom filters 😂

daniel holmgren 🫠17 Dec 2024

(oh wait i can't read dates, this was before the issue i made)

2 5

oh no i also misread the date

1 5

heh yeah I think it improves it but does not fix the issue I pointed out - small world indeed!

github.com/jasondavies/...

False positives · Issue #31 · jasondavies/bloomfilter.js

I'm getting a much higher false positive rate than I would expect from a bloom filter of the size that I'm using I'm using a 1024-bit bloomfilter with 16 hashes and 20 elements in each filter. I'm ...

1 9

https://github.com/Callidon/bloom-filters/blob/master/src/hashing/hashing.ts#L36-L56

It seems like basically every bloom filter impl I look at has this same bug. someone who is good at academia pls help me write a paper that explains this. Even this "advanced double hashing" approach (in the most popular js implementation I could find) has the same flaw: github.com/Callidon/blo...

Philipp Pohl-Krüger 18 Dec 2024

3 9

Please roast me and don't hold back: github.com/wnfs-wg/dete... (It's not using double hashing though)

https://github.com/wnfs-wg/deterministic-bloom/blob/main/deterministic-bloom/src/common.rs#L72-L93

1 2

LGTM, you're avoiding the issue with double-hashing by not doing double-hashing, heh

1 2

1 more reply

It's less noticeable in this version because you'll still get multiple indices being generated, but they'll be the *same* indices as any other instance where hashA%size collides.

1 1

(although tbf, it might be statistically insignificant. I'd need to do the math...)

Lukemas 🎅🎄17 Dec 2024

bloomin' filters, in this economy?

a plate of "bloomin' onions", one of the worst things the USA has ever invented in the process of cultural appropriation

Ryan Moulton 17 Dec 2024

I think it would be better to explicitly decay posts with time, perhaps adding the frequency with which you check discover to the decay. Reddit's mechanism was posted_time + log(upvotes) to model exponential decay in time without having to recompute every score when time advances.

1 9

Ryan Moulton 17 Dec 2024

You could modulate the time vs activity contribution with a coefficient that depends on how often the user checks.

1 2

this is just a dedupe, not sure how it relates to ranking

1 5

basically if you’re walking around the app, Discover doesn’t know about it, so it currently may show you stuff you’ve already seen

1 9

Ryan Moulton 17 Dec 2024

Yes, if the main point is to dedupe discover against other feeds, that makes sense. My thinking from the description was that the main issue was a lack of freshness in the discover feed itself, that people who check it frequently weren't seeing new things.

1 4