19 ms·

> Compute the SHA1 of the candidate password, and use the prefix to guess at the location in the file. Read a block of +/- a few kilobytes around that guessed l

> Compute the SHA1 of the candidate password, and use the prefix to guess at the location in the file. Read a block of +/- a few kilobytes around that guessed location. This will have a "hit" about 99% of the time, and at this guess will have to be refined at most 2-3 times. Basically, a binary search?

contravariant 4y ago
More like the secant method I suppose.
dellamonica 4y ago
I think the basic idea is that the hash has a fairly uniform probability distribution, so knowing the prefix means you can estimate its location in a sorted list. For instance if we were talking about n random sequences of digits then if you want to look for a number starting with 42 then you can start looking at the the 0.42n element and it is likely already very close to a match.
- piyh 4y ago
  Is a uniform hash the same thing as a consistent hash?
  - User23 4y ago
    No. Consistent hashing and its easier to understand cousin rendezvous hashing are about maintaining properties after a rehash.
ryangittins 4y ago
It's similar, but not quite a binary search. Imagine you have a book and you're trying to determine if a certain page number exists or if it's been torn out. You know the order, as pages are numbered in sequence, but you don't know whether the target page is still in the book or not. (For very large, cryptographically secure books you can assume the pages have been torn out uniformly.) With the method described, you would measure the thickness of the book (the size of the lookup file) and open to a proportional page. e.g. If you're looking for page 120 and the book is 360 pages long, that's 1/3 of the thickness. So, find the point that's a third of the thickness of the book and open the book there. You'll be pretty close. With a binary search, you wouldn't measure the thickness of the book. You'd always just blindly start in the middle, assess which half the target page is, and repeat the operation on that half and you'll get there pretty quickly. Both exploit the knowledge of how the data is organized and both are most well-suited to uniform data (like pages in a book or random hashes), but are just different strategies requiring different means of accessing the data. Admittedly not a perfect analogy, but you get the idea.
- sally_glance 4y ago
  Wiki lists a variation of binary search called "interpolation search" [1] which > Instead of calculating the midpoint, interpolation search estimates the position of the target value, taking into account the lowest and highest elements in the array as well as length of the array. Sound pretty close to what you're describing :-) [1] https://en.m.wikipedia.org/wiki/Binary_search_algorithm#Interpolation_search https://en.m.wikipedia.org/wiki/Binary_search_algorithm#Inte...

contravariant 4y ago

More like the secant method I suppose.

dellamonica 4y ago

I think the basic idea is that the hash has a fairly uniform probability distribution, so knowing the prefix means you can estimate its location in a sorted list. For instance if we were talking about n random sequences of digits then if you want to look for a number starting with 42 then you can start looking at the the 0.42n element and it is likely already very close to a match.

piyh 4y ago
Is a uniform hash the same thing as a consistent hash?
- User23 4y ago
  No. Consistent hashing and its easier to understand cousin rendezvous hashing are about maintaining properties after a rehash.

ryangittins 4y ago

It's similar, but not quite a binary search. Imagine you have a book and you're trying to determine if a certain page number exists or if it's been torn out. You know the order, as pages are numbered in sequence, but you don't know whether the target page is still in the book or not. (For very large, cryptographically secure books you can assume the pages have been torn out uniformly.) With the method described, you would measure the thickness of the book (the size of the lookup file) and open to a proportional page. e.g. If you're looking for page 120 and the book is 360 pages long, that's 1/3 of the thickness. So, find the point that's a third of the thickness of the book and open the book there. You'll be pretty close. With a binary search, you wouldn't measure the thickness of the book. You'd always just blindly start in the middle, assess which half the target page is, and repeat the operation on that half and you'll get there pretty quickly. Both exploit the knowledge of how the data is organized and both are most well-suited to uniform data (like pages in a book or random hashes), but are just different strategies requiring different means of accessing the data. Admittedly not a perfect analogy, but you get the idea.

sally_glance 4y ago
Wiki lists a variation of binary search called "interpolation search" [1] which > Instead of calculating the midpoint, interpolation search estimates the position of the target value, taking into account the lowest and highest elements in the array as well as length of the array. Sound pretty close to what you're describing :-) [1] https://en.m.wikipedia.org/wiki/Binary_search_algorithm#Interpolation_search https://en.m.wikipedia.org/wiki/Binary_search_algorithm#Inte...