4 ms·

Interesting how the PKZIP password-protected compressed file is now easily decrypted in <5 minutes, but the original one-time pad is still as mathematically rob

Interesting how the PKZIP password-protected compressed file is now easily decrypted in <5 minutes, but the original one-time pad is still as mathematically robust as ever. We could have had a very different history if they'd used DES or RC2 for encryption!

rtkwe 2y ago
One time pads used properly are theoretically perfectly unbreakable. The problem is making sure no one ever uses the same 'pad'/keystream twice, that your pad generation is actually random, and that the pads never fall into the hands of your adversaries. (or if they do you've been diligent about completely destroying the used pads and the other end of your communications doesn't use the captured set of pads) They're just not very good at anything other than point to point secret passing and require a real world connection to distribute. So much of symmetric key cryptography is just trying to find creative ways of creating and recreating 'one time pads' so we can distribute the key material instead of the pads themselves.
- janzer 2y ago
  > that your pad generation is actually random The one thing that stood out to me with the original blog post and a quick glance at the code was that it appeared as if the pad was certainly not actually random. Could anyone that has actually understood it a bit more confirm or reject this? Edit: It seems that the random generation can be found starting here https://github.com/Vulacode/RANDOM/blob/d6a1a1d694b22e6a115b50a6c2d2bada41cda075/RANDOM.BAS#L1262 https://github.com/Vulacode/RANDOM/blob/d6a1a1d694b22e6a115b... With three methods, one (RAND2) seems to use the basic interpreter rng more or less directly and the other two seem to be fairly simple prngs seeded from the basic interpreter's rng. I don't actually know what the state of basic interpreter rngs was in the early '80s but I would be fairly surprised if they're anything that is secure.
  - rtkwe 2y ago
    At the time PRNG was probably good enough. I wouldn't want to go up against the NSA today using the same entropy source but against South Africa decades ago it was probably good enough. Even knowing what PRNG source the original noise came from it'd take a hell of a lot of guess and check with cribs to come close to guessing the seed for the PRNG. That would be my first crack at breaking a OTP I knew was generated with a particular PRNG at least as a casual student of the craft. Generate huge amount of noise for the possible seeds and see if any names like "Mandela" or other known leaders suddenly pops out of intercepted messages starting at different points in the noise stream (and see if the rest of the message makes any sense when that does happen).
    - janzer 2y ago
      If the PRNG is good enough then shipping floppies full of PRNG output is very much unnecessary. Simply send the seeds used to initialize the PRNG thereby fitting many (~180k of them on a 720kb floppy) seeds on one floppy and save your couriers a lot of risk.
      - sdenton4 2y ago
        Encode the seed in the arrangement of a deck of cards... shuffle to delete.
        rtkwe 2y ago
        The card deck can be the key and the encryption mechanism too with Solitare. It's not secure for longer messages but it should be sufficient for short messages. It's a delicate method though because if you mess up it can be difficult to impossible to recover the proper state of the deck. https://en.wikipedia.org/wiki/Solitaire_(cipher) https://en.wikipedia.org/wiki/Solitaire_(cipher)
      - rtkwe 2y ago
        You can already fit huge amounts of text onto a single floppy. Uncompressed it's around 1.4 million characters. That is a method though and it's basically what stream ciphers are doing, translating a key into a random stream that's then applies to the plaintext. One benefit of the true OTP though is you don't have to transfer the software and ensure it's generating the same key stream on both ends.
  - geocar 2y ago
    > Could anyone that has actually understood it a bit more confirm or reject this? In BASIC, the word "RANDOMIZE" sets the seed for the RND function, and you'll find it's initially dependant on time (including the typing speed of the user): https://github.com/Vulacode/RANDOM/blob/main/RANDOM.BAS#L295 https://github.com/Vulacode/RANDOM/blob/main/RANDOM.BAS#L295 It then is reinitialised periodically by mixing in run time (which is highly variable due to microprocessor limitations) and checksums of previous parts of the stream: https://github.com/Vulacode/RANDOM/blob/main/RANDOM.BAS#L319 https://github.com/Vulacode/RANDOM/blob/main/RANDOM.BAS#L319 The RAND[123] appears to be Bennett Fox's Algorithm 647, which was designed for simulation purposes (statistical randomness), and is based on Lewis-Goodman-Miller's construction from 1969, so it had a great deal of scrutiny. I think this would have been state of the art in the late 1980s.
pastage 2y ago
South Africa did buy at least some of Crypto AGs backdoored products, not sure when though.

rtkwe 2y ago

One time pads used properly are theoretically perfectly unbreakable. The problem is making sure no one ever uses the same 'pad'/keystream twice, that your pad generation is actually random, and that the pads never fall into the hands of your adversaries. (or if they do you've been diligent about completely destroying the used pads and the other end of your communications doesn't use the captured set of pads) They're just not very good at anything other than point to point secret passing and require a real world connection to distribute. So much of symmetric key cryptography is just trying to find creative ways of creating and recreating 'one time pads' so we can distribute the key material instead of the pads themselves.

janzer 2y ago
> that your pad generation is actually random The one thing that stood out to me with the original blog post and a quick glance at the code was that it appeared as if the pad was certainly not actually random. Could anyone that has actually understood it a bit more confirm or reject this? Edit: It seems that the random generation can be found starting here https://github.com/Vulacode/RANDOM/blob/d6a1a1d694b22e6a115b50a6c2d2bada41cda075/RANDOM.BAS#L1262 https://github.com/Vulacode/RANDOM/blob/d6a1a1d694b22e6a115b... With three methods, one (RAND2) seems to use the basic interpreter rng more or less directly and the other two seem to be fairly simple prngs seeded from the basic interpreter's rng. I don't actually know what the state of basic interpreter rngs was in the early '80s but I would be fairly surprised if they're anything that is secure.
- rtkwe 2y ago
  At the time PRNG was probably good enough. I wouldn't want to go up against the NSA today using the same entropy source but against South Africa decades ago it was probably good enough. Even knowing what PRNG source the original noise came from it'd take a hell of a lot of guess and check with cribs to come close to guessing the seed for the PRNG. That would be my first crack at breaking a OTP I knew was generated with a particular PRNG at least as a casual student of the craft. Generate huge amount of noise for the possible seeds and see if any names like "Mandela" or other known leaders suddenly pops out of intercepted messages starting at different points in the noise stream (and see if the rest of the message makes any sense when that does happen).
  - janzer 2y ago
    If the PRNG is good enough then shipping floppies full of PRNG output is very much unnecessary. Simply send the seeds used to initialize the PRNG thereby fitting many (~180k of them on a 720kb floppy) seeds on one floppy and save your couriers a lot of risk.
    - sdenton4 2y ago
      Encode the seed in the arrangement of a deck of cards... shuffle to delete.
      - rtkwe 2y ago
        The card deck can be the key and the encryption mechanism too with Solitare. It's not secure for longer messages but it should be sufficient for short messages. It's a delicate method though because if you mess up it can be difficult to impossible to recover the proper state of the deck. https://en.wikipedia.org/wiki/Solitaire_(cipher) https://en.wikipedia.org/wiki/Solitaire_(cipher)
    - rtkwe 2y ago
      You can already fit huge amounts of text onto a single floppy. Uncompressed it's around 1.4 million characters. That is a method though and it's basically what stream ciphers are doing, translating a key into a random stream that's then applies to the plaintext. One benefit of the true OTP though is you don't have to transfer the software and ensure it's generating the same key stream on both ends.
- geocar 2y ago
  > Could anyone that has actually understood it a bit more confirm or reject this? In BASIC, the word "RANDOMIZE" sets the seed for the RND function, and you'll find it's initially dependant on time (including the typing speed of the user): https://github.com/Vulacode/RANDOM/blob/main/RANDOM.BAS#L295 https://github.com/Vulacode/RANDOM/blob/main/RANDOM.BAS#L295 It then is reinitialised periodically by mixing in run time (which is highly variable due to microprocessor limitations) and checksums of previous parts of the stream: https://github.com/Vulacode/RANDOM/blob/main/RANDOM.BAS#L319 https://github.com/Vulacode/RANDOM/blob/main/RANDOM.BAS#L319 The RAND[123] appears to be Bennett Fox's Algorithm 647, which was designed for simulation purposes (statistical randomness), and is based on Lewis-Goodman-Miller's construction from 1969, so it had a great deal of scrutiny. I think this would have been state of the art in the late 1980s.

pastage 2y ago

South Africa did buy at least some of Crypto AGs backdoored products, not sure when though.