7 ms·

> The technique that the researchers developed is quite complex and required two months of computations on 900 individual GPUs.

• motohagiography 5y ago
  I only half joke when I ask, when you break a cryptogrpahic hash, does it mean that now it's just a really amazing compression algorithm, but with a very heavy compute requirement? The non-joking half is speculating what data compression in a post-quantum compute world looks like.
  • FartyMcFarter 5y ago
    Compression algorithms must encode data in a reversible way, which hash functions can't do in general. For example, SHA-1 outputs a 160 bit hash, which means some input of 161 or more bits will definitely have the same hash as some other input of the same size. Even smaller inputs may have collisions too.
  • fwip 5y ago
    No, because reversing the hash has infinite possible answers (well, "very many" for bounded input size). You can't decompress 32 bytes into 1GB because you don't know which of the 1GB-sized answers is the intended one.
    • ganzuul 5y ago
      Natural data is easily identifiable.
      • __s 5y ago
        That's because natural data has low entropy But let's say every paragraph only offers 1 bit of entropy. Then a 160 bit hash gives you fuzzy accuracy up to 160 paragraphs. After that you'll have to extend the hash with hints to guide which sequence of paragraphs you're looking for, & hints for where the typos are ofc, 100x compression of English text doesn't require this amount of compute to decompress: https://en.wikipedia.org/wiki/Hutter_Prize https://en.wikipedia.org/wiki/Hutter_Prize It's also impractical since most compression use cases want to put the work in compression, & have decompression be straight forward edit: 100x was misreading, it's currently 8.6x http://prize.hutter1.net/#prev http://prize.hutter1.net/#prev
        • AnimalMuppet 5y ago
          "Paragraph" is highly optimistic. IIRC, each English character has about 1 bit of entropy.
          • __s 5y ago
            Shannon estimated 0.6 to 1.3: https://cs.fit.edu/~mmahoney/dissertation/entropy1.html https://cs.fit.edu/~mmahoney/dissertation/entropy1.html For the sake of argument I figured I'd be highly optimistic. The linked prize shows practical evidence of 1GB of Wikipedia being compressed below 1 bit per character (& that's with a limit of 50 hours cpu time, 10GB memory, & 100GB disk)
        • ganzuul 5y ago
          This is very abstract, but I believe that since both input and output are very close in program space compared to the total size of PS, the heuristics to map between them are going to be of a manageable size. This is based on an intuition about a single source for all activity in this universe.
      • dTal 5y ago
        Not it's not. You can't distinguish the complete works of Shakespeare from the complete works of Shakespeare with the words changed a bit, or switching to Harry Potter for a bit in the middle, or a completely dazzling and original work of fiction. Any hash might generate all three of these, and essentially boundless other works. It's a library of Babel.
        • ganzuul 5y ago
          Your examples really fall out of the scope of the premise.
          • fwip 5y ago
            No, they're 100% correct.
          • dTal 5y ago
            Forgive me if I've misunderstood - the premise was that, out of the infinite set of data that hashes to a particular hash/checksum, there is a unique data set that is "obviously" the real one? Or at least, that the set is meaningfully bounded? My reply is that this is not the case. There will be infinitely many "plausible" data sets as well. You could collide every hash in existence merely by making undetectably tiny alterations to Shakespeare.
            • ganzuul 5y ago
              Not obviously, no. - Just a very high probability. Perhaps that provides noise immunity to some degree. If it does, it is a form of AI. This admittedly open question presumes a very large fuzzy 'code book' with which it can re-assemble the data. The length of the input in cleartext is valuable metadata that speeds up the search.
              • dTal 5y ago
                You still seem to be missing the point. The problem is that the SHA-1 hash is one of 2^160 possible values, while a 1GB plaintext is one of 2^8000000000 possible values. That means that the hash disambiguates your message down to one of 2^7999999840 values. Let's go smaller. Let's say our plaintext is a single kilobyte. One 80x25 terminal's worth of ASCII. Knowing the SHA-1 hash narrows our search space, yes, but the search space is so absurdly large that it only solves 0.0000... (insert over two thousand zeros here) ..0001% of the problem. It tells you basically nothing.
      • contravariant 5y ago
        Only if you count all natural looking data of which there is way more than you could possibly imagine. It is of course likely that humanity hasn't yet created more than 2^100 (~10^30) files, so in theory given a registry of all files in existence you might be able to identify it by its hash. However while this is simple it's definitely not easy.
        • swutas 5y ago
          But this is technically an invalid answer to the problem of file compression. An easy (!) way for data to be losslessly compressed would just be to have a registry of all files in existence, and to refer to each file by its index in the registry. (Like the prisoners who had told each other all their jokes so many times that now they could just quote them by number and everyone would laugh.) Data compression is supposed to be able to deal with novel but likely documents without needing to add them to a global registry.
        • ganzuul 5y ago
          I can imagine the output of program space. That's pretty big. All possible universes in fact. It's an issue of probability and bins. While natural data is infinite, there is vastly more unnatural data. At some point you have enough metadata (e.g. natural vs. random) to know that the original data came from Earth to pick out the right needle from the needle stack. Unless the data is from a completely alien source, we are close enough to that source for our heuristics to be of a manageable size.
          • contravariant 5y ago
            It's somewhat irrelevant how many unnatural data there is. The point is that there's way more plausible data (or sentences if we're restricting ourselves to natural language) than there are possible 160; 256 or 512 bit hashes. Unless of course you enumerate all of human communication, but like I said that doesn't count as 'easy'.
            • ganzuul 5y ago
              I'm not trying to claim this is practical with current technology.
      • fwip 5y ago
        Nope, not on these scales. Say you have a 32 byte hash, that's 2^(328) possible values, right? Now say your input is 128 bytes, that means that (on average) each 32 byte hash maps to 2^(968) values. "Natural looking" data will occur an astronomical number of times in a search space that large - which is, again, only 96 bytes larger than your hash.
      • xinniethepooh 5y ago
        It's not, and that's why decryption of unknown ciphertext is even harder
    • akomtu 5y ago
      Not so simple. A hash corresponds to infinitely many messages, but how many of them are in ASCII charset under 1KB long? It may happen that each hash has a unique message within these constraints.
      • hyperpape 5y ago
        Ignoring punctuation, capitalization and spaces, you have (26 ^ 1024) / (2 ^ 160) ascii texts, which is too large for python to do the division. Thinking harder, that's: >>> (13 * (160)) * (26 ** (1024 - 160)) 586015382205826960727672544401463871212215837535709025412643135464856100047507808667927549205890681326798481562717865671371914861707033271010401105757243098374422354323280335989456977123883814519788789676409601028611595593846201622073508573113400508407626532918150795408521721900638322896979964584478287370459866751451622413984067802115006844002721198098126119299044037305285971873899685570443731713584345786693414215895940310733413089663439828136700053588516077484775302179979357918243214847406310224703621807862576801557249657421436718532619781248154845297450962161296162654285951879462181582579086975207170674079727507724939279192338763731562331681240184746490930657625088527012496974579965412172847315257089070105214466289197177909463176672954181773739345690793807307314187284671422149249630372138364687234076394633405015375177710973043617082884089261346079718819448519032937091364439564690325014717871376537803759701695837030040255807318892621674241958398030180530294671920834183657715967728968579955163053146309746677182369005157209730333605691785063279407829717681098919238400049142795696195708090541066855775773950462556018168019660329830112434789524857886670766484791538540247307849949305926757172442880517278313785940979709167536140659937329357336156000509320395656047604973761134700992358740522602445520136787846575269569119611476145342798153931437530464566322510167663230985347176517861376 If you restrict it to words, assume that there's only 1000 words in the English language, averaging 5 letters each, you get: (1000 ^ 200) / (2 ^ 160) which becomes: >>> (500 ** 160) * (1000 ** 40) 684227765783602085411977335590779360976690401306892466678255997993062052092705371819647552911192178726196289062500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 There will be massive numbers of realistic texts that match any given hash.
    • motohagiography 5y ago
      This is what made it a funny thought experiement to me. I was doing some space related stuff a while back and when you're dealing with something as small as 100mb, and you add the constraint of up to a light-year or more of latency, which makes error correction immensely costly, having a quantum processor reciever find the collision of a unique hash could be faster than transmitting the data with errors. There's probably a distance where the latency in light years is longer than it takes for a quantum processor with some shortcuts to exhaust the search space for the collision on the hash - and potential hashing algorithms that contain information and hints about a hyperplane that generates the original data over the field of possibilities. To a quantum computer with sufficient qbits at a long enough latency distance away, the 32-bit hash of a 2048bit RSA key may "arrive" faster than transmitting the whole key. It feels like a fundamental misunderstanding of something in communication theory, but this was the thinking that prompted it.
      • mypalmike 5y ago
        Using the pigeonhole principle, consider how many 100 megabit values must, on average, hash to the same 32 bit value. The answer is a huge number (I could be wrong but it seems to me it might be 2 ^ (100,000,000 - 32)?). This is a bit of a paradox in cryptographic hashing, where finding a collision is difficult, but the number of collisions is enormous.
      • fwip 5y ago
        Yeah, you're fundamentally missing what I wrote, as well as pigeonhole principle and the basics of information theory. Let's say you replace the quantum computer with an oracle. You have an infinitely long dictionary, and you can turn to any page and see your hash, as well as every possible input that could form that hash. There's billions and billions of options that all match your hash - how could you pick which one is definitely the "right" one? You're no closer to knowing what the transmitted message was, because of the astronomical number of inputs that you now have to sift through. [ Technically, you're (length of hash in bits) closer. Say you have 10 bits of hash, or 1024 values. There are (on average), 2 11-bit inputs that create that hash, 4 12-bit inputs, 8 13-bit inputs, and so on, following the powers of 2. At input of N=30 bits, you have 2^20 =~ 1 million possible inputs with that exact same hash. 1KB? 2^990, or "one followed by 990 zeroes". ]
  • deleted 5y ago
    [deleted]
  • tomsmeding 5y ago
    These hashes, regardless of their actual cryptographic strength, are intended to be indistinguishable from a random generator keyed with the input, kind of. Assuming that they succeed in that, hashes should be quite well distributed. That means that that for each hash n-bit hash output, there will be about two (n+1)-bit input strings that produce that hash, about four (n+2)-bit input strings, eight (n+3)-bit input strings, etc. So while there are probably few ASCII input strings that map to one particular hash, for example, there will be loads and loads of arbitrary bitstrings that map to that hash. Hashes are very bad compressors. :)
  • kazinator 5y ago
    The compression joke evokes a misconception (as STEM jokes often do) which, in this case, is that breaking a hash means finding a way to recover the full text of a multi-megabyte document, from a 100-something byte hash. Whereas all it means is that it's become feasible for someone to produce a fake document with the same hash as the genuine one; the attack depends on the existence of collisions, which depend on the hash being one-way, such that an infinite set of documents could be "recovered" from the hash. Most of the documents you could "decompress" from a hash are going to be gibberish, but some of them are going to be legit. If a hash is "broken", that means it's somehow unduly easy to search that ocean of gibberish collisions to find a chosen text which goes to a certain desired hash. Nothing quantum can redefine a function that isn't one-to-one and onto into one that is. The hashing function remains ever the mathematical object that it is: a one-way function. But calculations of or searches through that function can be faster. In a post-quantum world, pre-quantum crypto and hashing could well turn out to be "for shit" as such, but not due to ruses like suddenly reversing irreversible functions. Not saying that the joke isn't funny! We can imagine some hard-core computer science or math sitcom in which the fall characters say things like this, and only the very narrow target audience gets it.
• asdfman123 5y ago
  I wonder how much money in Bitcoin they would have made if they had used those hashes to mine instead. Speaking of which, it would be funny if they were pretending to do security research but added a secret backdoor to mine bitcoin instead, somehow exporting those hashes or using the partial results of SHA-1 calculations (BTC isn't SHA-1). I'm just joking, but I wonder if that's possible. If anyone is Machiavellian enough for that, it's security researchers.
  • fsckboy 5y ago
    mining bitcoin on one GPU is uneconomical, so mining bitcoin an a large number of them is... also.
    • FredPret 5y ago
      Unless your research grant pays for the electricity
      • asdfman123 5y ago
        Ding ding ding
        • gjs278 5y ago
          wrong wrong wrong. the hash rate is so low on a gpu they wouldn’t even make a penny.
    • valec 5y ago
      this is a retarded and pedantic comment. op clearly meant cryptocurrency and put bitcoin as a stand in instead of ethereum, maybe out of ignorance. this comment doesn't address the meat of their comment and contributes nothing.
      • exciteabletom 5y ago
        > When disagreeing, please reply to the argument instead of calling names. "That is idiotic; 1 + 1 is 2, not 3" can be shortened to "1 + 1 is 2, not 3." > Be kind. Don't be snarky. https://news.ycombinator.com/newsguidelines.html https://news.ycombinator.com/newsguidelines.html
• lallysingh 5y ago
  Or roughly 1.3M GPU hours. Less as GPUs get upgraded. Not sure how many AWS F1 (FPGA) hours it would take.
  • wongarsu 5y ago
    So somewhere between $300,000 (running consumer GPUs cheaply) and $30 million (paying AWS on-demand prices for Tesla V100). Even the upper bound for that seems well worth it for well-funded attackers if the target is juicy enough.
    • lallysingh 5y ago
      Consumer GPUs could be run from a botnet, actually... Yikes.