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

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.

Replies are listed 'Best First'.
Re^4: crypto with core modules only
by tobyink (Canon) on Aug 31, 2018 at 11:14 UTC

    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!

      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.

        It appears you didn't notice, but in the Wiki:One-time Pad article you linked, the second sentence of the second paragraph specifically says, " On July 22, 1919, U.S. Patent 1,310,719 was issued to Gilbert S. Vernam for the XOR operation used for the encryption of a one-time pad.".

        First off, this is precisely what tobyink said in Re^2: crypto with core modules only: that one-time pads can be easily implemented with XOR. And you've been arguing against him on this, despite the fact that the article you mentioned points this out, quite early on.

        Second, you just mentioned your "modulo solution I suggested based on a 100-year old algorithm", trying to imply that it was somehow better by being older. But I'm pretty sure your implementation isn't a hundred years old. You might argue, "but mine is based on the algorithm". I would argue that so is the XOR solution.. And the XOR solution mentioned in the Wiki article, patented in 1919, has the advantage of (currently) being a 99-year-old implementation of the algorithm, whereas your description was made quite recently.

        "if the character is drawn randomly from the printables". Apparently, you don't understand that the key for the XOR (the my $encrypted = $message ^ $key; from tobyink's post) is a string of characters randomly chosen octets (though from the full range of 8-bit characters, rather than the limited quantity of "printable characters" that you suggest).

        (regarding the update: if the user makes frequent small changes and re-applies it, then it's no longer a one-time pad; it's a multi-time pad with slight modifications, which does not have the strength of security that a true one-time pad has. But arguing that one-time pad can be misused by being reused has nothoing to do with the arguments of "add and modulo" vs "xor", so I'm not sure why you brought it up.)

        To sum up, regarding the XOR implementation: It is still a one-time pad, so the underlying algorithm is as old as yours. It has the same random nature of the key as yours does -- but is slightly better, because it has 256 possible characters (in an 8bit-character string representation), rather than the 96 you've limited yourself to. The XOR is faster: it's one math operation per character, rather than the offset, add, modulo, re-offset that you described.

Re^4: crypto with core modules only
by haukex (Bishop) on Aug 31, 2018 at 14:04 UTC
    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.

        This is about using the same key on multiple messages. In these ancient times, one machine had to issue keys to users independently of these users then needing them to encrypt something. An organisational problem rather than a problem of the algorithm. Today it is simple enough that the program encrypts and generates the key in one run. Although as we can see from the amount of confusion in this thread -- even intelligent people have difficulty understanding what is breakable or not and why. My impression is that the OTP had a bad rep. from these incidents. Even more confusing for many is of course: why the more recent use of number theory (modulo) in also public key encryption as opposed to using XOR? I have tried to explain it from my own perspective because I can find no similar explanations online - just more confusing posts in other sites. In one case I saw a lengthy answer to this very question on stack-exchange that failed to even try to actually answer the question but waffled about what was popular with cryptographers instead.

      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

      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
    A reply falls below the community's threshold of quality. You may see it by logging in.
Re^4: crypto with core modules only
by haukex (Bishop) on Aug 31, 2018 at 10:31 UTC
    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?

      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

        I poked a hole where I felt one needed to be poked, although I tried to do so somewhat gently, so as to leave the door open to potentially allow for some constructive discussion.

        If you feel that I'm in the wrong here, whether in the facts or in my style, then I'm open to hearing criticism specific to my posts; but please no random speculations or vague analogies to other situations.

        OK so I confess that I originally rejected the XOR rather quickly. But I just didn't see the point in using an algorithm that was potentially inferior to the old one given that it had potential unresearched loopholes. Meanwhile after more consideration of the xor insead of modulo, I found a loophole (see elsewhere in thread)
      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.
        I considered XOR before choosing the algorithm and rejected it because XOR only changes those bits that are different = about 50% of them.
        The optimal number of bits to flip is ... BANG! ... i.e. abort thinking about it ... makes the question irrelevant.

        I was asking for clarification regarding you saying you rejected XOR because it only changes about 50% of the bits.

        A reply falls below the community's threshold of quality. You may see it by logging in.