3 ms·

Surprise! Cryptography designed by the NSA is tailor-made to be easily cracked considering the computing resources they command.

floatingatoll 8y ago
The surprise is that they may have proven that a weakness exists. To date, it’s merely been a suspicion. It will be interesting to see whether the weakness is deemed plausible or not by security researchers - and whether it can be applied to non-NSA systems.
- deleted 8y ago
  [deleted]
- nullc 8y ago
  > The surprise is that they may have proven that a weakness exists. A 64-bit keyspace is small enough that I don't think it's reasonable to take their paper as proof. It would be fairly straight forward to use a FPGA farm (or potentially GPU farm) to search the entire keyspace. The fringes of the cryptocurrency altcoin ecosystem have caused the creation of some pretty impressive FPGA and GPU farms... Additionally since they equate two pieces of text from the document via a key, they can get a massive speedup if they don't actually fix them. On this basis their proof mechanism seems highly suspect to me, unless I'm misreading it. To be more clear of about I'm suggesting: pick a piece of text from the source, pick a key, encrypt or decrypt, then check if the result is anywhere in the text. Assuming the lookups are free this gets you a 4.2 million fold speedup (the corpus they're using is about 4.2MB). I'm not familiar with the structure of the cipher but there may be a meet in the middle that dramatically improves this approach. It's completely reasonable that someone might search a 64-bit keyspace as a prank, ... I factored a 100-digit semiprime last night for a prank. My prank was not anywhere near as "cool" as convincing a lot of people that an NSA cipher was backdoored.
  - tptacek 8y ago
    Forget the FPGA farm. The actual task the authors have set out for themselves to "prove" SIMON weak, you could complete on a laptop. The problem is, you can complete it on a laptop for any cipher with the same block and key size parameters.

floatingatoll 8y ago

The surprise is that they may have proven that a weakness exists. To date, it’s merely been a suspicion. It will be interesting to see whether the weakness is deemed plausible or not by security researchers - and whether it can be applied to non-NSA systems.

deleted 8y ago
[deleted]
nullc 8y ago
> The surprise is that they may have proven that a weakness exists. A 64-bit keyspace is small enough that I don't think it's reasonable to take their paper as proof. It would be fairly straight forward to use a FPGA farm (or potentially GPU farm) to search the entire keyspace. The fringes of the cryptocurrency altcoin ecosystem have caused the creation of some pretty impressive FPGA and GPU farms... Additionally since they equate two pieces of text from the document via a key, they can get a massive speedup if they don't actually fix them. On this basis their proof mechanism seems highly suspect to me, unless I'm misreading it. To be more clear of about I'm suggesting: pick a piece of text from the source, pick a key, encrypt or decrypt, then check if the result is anywhere in the text. Assuming the lookups are free this gets you a 4.2 million fold speedup (the corpus they're using is about 4.2MB). I'm not familiar with the structure of the cipher but there may be a meet in the middle that dramatically improves this approach. It's completely reasonable that someone might search a 64-bit keyspace as a prank, ... I factored a 100-digit semiprime last night for a prank. My prank was not anywhere near as "cool" as convincing a lot of people that an NSA cipher was backdoored.
- tptacek 8y ago
  Forget the FPGA farm. The actual task the authors have set out for themselves to "prove" SIMON weak, you could complete on a laptop. The problem is, you can complete it on a laptop for any cipher with the same block and key size parameters.