4 ms·

Ask HN: How can i verify perfect secrecy of a cryptosystem?

3 points by sgy 11y ago

i'm playing with an encryption algorithm (demo: https://www.youtube.com/watch?v=h1kABn5dfXc). how can i prove it's information-theoretically secure?

bmm6o 11y ago
Your key is too short - it's not possible for it to be information-theoretically secure. That's just one of its obvious faults: it looks like it doesn't even work all of the time, the system generates a key instead of taking on as input, the data undergoes unnecessary expansion, etc etc etc.
- sgy 11y ago
  why is that the case? would you please guide me to some good read on that? > i'm not using any traditional math that current encryption relies on; no entropy, discrete logarithms nor prime factorials, etc.
  - bmm6o 11y ago
    Have you read the Wikipedia article? It's not written for lay people but it's not bad. Using it you should be able to prove to yourself that if the key has less entropy than the message it's not possible to achieve this level of security. https://en.wikipedia.org/wiki/Information-theoretic_security https://en.wikipedia.org/wiki/Information-theoretic_security > i'm not using any traditional math That doesn't get you an out - the theorems don't care how you transform M to C.
    - sgy 11y ago
      right. but, again, the whole system doesn't even rely on entropy. i was referring to existing literature as an analogy to, perhaps, better clarify the idea. it seems i was mistaken doing so.
      - DanBC 11y ago
        The sci.crypt faq has more information. http://www.contrib.andrew.cmu.edu/~shadow/crypt.html http://www.contrib.andrew.cmu.edu/~shadow/crypt.html http://www.faqs.org/faqs/cryptography-faq/ http://www.faqs.org/faqs/cryptography-faq/ It might be an idea to read about different attacks - known plaintext etc - and seein if your system is still secure. (It won't be, so if you can't find the flaw you know you need to look more).
        sgy 11y ago
        thanks. looking into them ..
- sgy 11y ago
  - the first time, i intentionally modified the key [to show that it doesn't work just on any number input] - the system can be updated to take a key as input. - right, it expands by nearly a half; that's used to make it just as secure as the one-time pad, but more practical. [and this is what i want to verify, then optimize]. if you have the time, i'd love to hear more feedback. thank you very much.
  - DanBC 11y ago
    The video is too tiny to see on iPhone 4s. People generally don't want video for this kind of stuff, a text description of what you're doing would be much better. > - right, it expands by half but i believe it's just as secure as the one-time pad [this is what i want to verify] This is the easiest bit to critique / attack. For OTP to work the pad needs to be properly random; the pad needs to be bigger than the plain text. Expanding something else probably stops it being properly random. People get hung up on OTP because PROVABLY SECURE. They are secure, but they're also cumbersome to use.
    - sgy 11y ago
      Dan, thanks for the feedback. - my bad, the font size in the editor is originally small. will try to fix that. - problem is that the algorithm itself is what makes the system strong. once revealed in a white paper, the whole thing is useless. what do you recommend to write in a text description for this case? - it's an imitation of OTP mechanism but has nothing to do with how OTP is conventionally implemented.
      - bmm6o 11y ago
        > it's an imitation of OTP mechanism but has nothing to do with how OTP is conventionally implemented That's called a Viginere cipher and people stopped using it in the 19th century.
        sgy 11y ago
        i don't think it's related to Viginere. here's an example of repeated text that is not repeated when encrypted: http://i.imgur.com/i4XLLEm.png http://i.imgur.com/i4XLLEm.png

3 points by sgy 11y ago

i'm playing with an encryption algorithm (demo: https://www.youtube.com/watch?v=h1kABn5dfXc). how can i prove it's information-theoretically secure?

bmm6o 11y ago

Your key is too short - it's not possible for it to be information-theoretically secure. That's just one of its obvious faults: it looks like it doesn't even work all of the time, the system generates a key instead of taking on as input, the data undergoes unnecessary expansion, etc etc etc.

sgy 11y ago
why is that the case? would you please guide me to some good read on that? > i'm not using any traditional math that current encryption relies on; no entropy, discrete logarithms nor prime factorials, etc.
- bmm6o 11y ago
  Have you read the Wikipedia article? It's not written for lay people but it's not bad. Using it you should be able to prove to yourself that if the key has less entropy than the message it's not possible to achieve this level of security. https://en.wikipedia.org/wiki/Information-theoretic_security https://en.wikipedia.org/wiki/Information-theoretic_security > i'm not using any traditional math That doesn't get you an out - the theorems don't care how you transform M to C.
  - sgy 11y ago
    right. but, again, the whole system doesn't even rely on entropy. i was referring to existing literature as an analogy to, perhaps, better clarify the idea. it seems i was mistaken doing so.
    - DanBC 11y ago
      The sci.crypt faq has more information. http://www.contrib.andrew.cmu.edu/~shadow/crypt.html http://www.contrib.andrew.cmu.edu/~shadow/crypt.html http://www.faqs.org/faqs/cryptography-faq/ http://www.faqs.org/faqs/cryptography-faq/ It might be an idea to read about different attacks - known plaintext etc - and seein if your system is still secure. (It won't be, so if you can't find the flaw you know you need to look more).
      - sgy 11y ago
        thanks. looking into them ..
sgy 11y ago
- the first time, i intentionally modified the key [to show that it doesn't work just on any number input] - the system can be updated to take a key as input. - right, it expands by nearly a half; that's used to make it just as secure as the one-time pad, but more practical. [and this is what i want to verify, then optimize]. if you have the time, i'd love to hear more feedback. thank you very much.
- DanBC 11y ago
  The video is too tiny to see on iPhone 4s. People generally don't want video for this kind of stuff, a text description of what you're doing would be much better. > - right, it expands by half but i believe it's just as secure as the one-time pad [this is what i want to verify] This is the easiest bit to critique / attack. For OTP to work the pad needs to be properly random; the pad needs to be bigger than the plain text. Expanding something else probably stops it being properly random. People get hung up on OTP because PROVABLY SECURE. They are secure, but they're also cumbersome to use.
  - sgy 11y ago
    Dan, thanks for the feedback. - my bad, the font size in the editor is originally small. will try to fix that. - problem is that the algorithm itself is what makes the system strong. once revealed in a white paper, the whole thing is useless. what do you recommend to write in a text description for this case? - it's an imitation of OTP mechanism but has nothing to do with how OTP is conventionally implemented.
    - bmm6o 11y ago
      > it's an imitation of OTP mechanism but has nothing to do with how OTP is conventionally implemented That's called a Viginere cipher and people stopped using it in the 19th century.
      - sgy 11y ago
        i don't think it's related to Viginere. here's an example of repeated text that is not repeated when encrypted: http://i.imgur.com/i4XLLEm.png http://i.imgur.com/i4XLLEm.png