in reply to Re: crypto with core modules only
in thread crypto with core modules only

One-time pads can be implemented much more easily than that. Just create a string of random characters the same length as your message (we'll call it $key), then do this:

my $encrypted = $message ^ $key;
my $decrypted = $encrypted ^ $key;

[download]

This will result in a ciphertext which is full of non-printable characters, but you can base64 encode it (MIME::Base64 has been in core since before Perl 5.8).

The problem with one-time pads is that the keys are very long (same length as the message) and need to have a decent amount of randomness, so cannot be committed to memory. They need to be stored somewhere.

toby döt ink

Replies are listed 'Best First'.
Re^3: crypto with core modules only
by TheloniusMonk (Sexton) on Aug 31, 2018 at 08:01 UTC
    I considered XOR before choosing the algorithm and rejected it because XOR only changes those bits that are different = about 50% of them. Although that seems plausibly enough to have the same effect, it seemed easier to block possible security loopholes therein than to have to do days of work analysing them statistically.

    And because you then have to choose something like MIME::Base64 to make it printable, this would increase the average lengths of both key and message by (95-64)/64 * 100% = 60.8%, exacerbating your own final point about lengths.

    Conversely, the OP is trying to encode a small list of info, I imagine to be something like:-

    pwd google p&BBw0RD
    pin iphone 8642
    etc.

    So I chose the solution that best fits what I imagine to be the use case. Yes the user needs to note the key which is issued at encryption time, equal in length to his secret info list and although it might well be 50+ characters in length, the OP is highly suggestive of wanting to reject keys that are too short - hence I stick by my post. I feel I responded as optimally as I could within a reasonable level of background research.

    update re having to store the key somewhere - this is already consequent from the boundary conditions of the OP. And its precisely what the OTP and the OP for that matter is about - write it on the back of a business card and close the terminal window used to generate the key, so there is only one physical copy, no electronic copies reducing the weakness to one physical item to keep in your physical wallet.

    more update: flipping half the bits with xor is analytically breakable for repeated use on same document where changes are small. modulo solution does not have same weakness.
[reply]

      If you flip either 0% of bits or 100% of bits, the crypto is easily breakable. (In the 0% case, the ciphertext is bit-by-bit identical to the plaintext!) For numbers very close to 0% or very close to 100%, it's not a lot harder. About 50% seems the optimal number of bits to flip, provided you don't do it by a predictable pattern.

      The base64 encoding would happen after encrypting, and the base64 decoding would happen before decrypting. So although it does make the ciphertext longer, it doesn't affect the required key length, which is still equal to the length of the plaintext.

      My algorithm has the advantage that you could not only reasonably commit a very short key to memory, but you could also commit to memory the script necessary to decrypt it!

      toby döt ink
[reply]
        The bit-composition is an issue for XOR which was not my proposition! The modulo solution I suggested based on a 100-year old algorithm makes the issue blissfully irrelevant - it doesn't matter in the least how many bits got flipped if the character is drawn randomly from the printables. Total red herring for me I am afraid, so please drop it.

        Update: although I will say that if an enemy suspects your algorithm and has access to the encrypted messages, and the user makes frequent small changes and reapplies it, the enemy can use the fact that half the bits don't change to break the encrypted message by analysis - not even brute force being required. This is not a weakness of the official OTP algorithm.

[reply]
      more update: flipping half the bits with xor is analytically breakable for repeated use on same document where changes are small. modulo solution does not have same weakness.

      ... but both you and tobyink were discussing a one-time pad. AFAIK, repetition is a common way to break encryption schemes and it's a substantial part of how the Enigma machine was broken. Although I'm not an expert and open to being proven wrong, I'd be willing to bet the modulo solution is breakable in a similar way to XOR if the pad is re-used.

[reply]
[reply]

        I haven't fully figured out a proof, but my intuition is that the following statement is true:

        Encrypting each byte with modulo arithmetic is secure if and only if encrypting each byte with xor is secure.

        They're both plaintext byte + key byte → cyphertext byte mappings such that if you know any two of the bytes, the third can be calculated deterministically with no outside factors. I'm pretty sure that any algorithms where that is true are essentially equivalent from a security standpoint.

        Xor is just fast and trivially easy to implement in Perl.

        Encode (plaintext is the string "txt" and key is the string "key"):

        $ perl -MMIME::Base64=encode_base64 -E'say encode_base64(shift^shift)'
+ txt key
Hx0N

        [download]

        Decode: (cyphertext is "Hx0N" and the key is still the string "key")

        $ perl -MMIME::Base64=decode_base64 -E'say decode_base64(shift)^shift'
+ Hx0N key
txt

        [download]
        toby döt ink
[reply]
[d/l]
[select]
      A reply falls below the community's threshold of quality. You may see it by logging in.
      XOR only changes those bits that are different = about 50% of them.

      Sorry, but I don't understand this point. Are you suggesting that flipping more bits will make it more secure? What would be an optimal number of bits to flip?

[reply]
        Sorry, but I don't understand this point.

        You aren't the only one.

        There was a recent post from Anonymous Monk theorizing that TheloniusMonk and sundialsvc4 were both Mike Robinson.
        Do we have any evidence that would suggest that this theory is wrong ?

        Mind you - I was very much appalled at the vitriolic disparagement that was thrust at sundialsvc4, and I would not like to see the same treatment handed out to TheloniusMonk even if they are one and the same.

        Cheers,
        Rob
[reply]
        The optimal number of bits to flip is ... BANG! ... i.e. abort thinking about it use the simple 100 year-old tried and tested unbreakable modulo algorithm instead which makes the question irrelevant.
[reply]
          A reply falls below the community's threshold of quality. You may see it by logging in.

In Section Seekers of Perl Wisdom