An attempt to overcome the key distribution problem inherent in one time pad cryptography

Question

After reading about the 'imminent cryptocalypse' etc, I started thinking about a cryptographic protocol that would not depend on complexity of mathematical operations (e.g. factorisation, discrete logarithm) for privacy.

I made a proof of concept that works by round-tripping the locally encrypted/decrypted message at both client and server, with precautions to protect the key from being discoverable during transmission. Details, and code, are hosted online.

An associated advantage of the scheme is that encryption preserves the message length, so might be suited for small messages (SMS etc) that can tolerate a small increase in transmission latency. I might invest some time in developing this into a SMS exchange platform, if the protocol stands up to scrutiny.

While it was just a little hobby project, I am wondering if it is really as secure as I have imagined it to be. Perhaps someone more knowledgeable about the number theoretic properties of modular groups can comment? In particular, my scheme relies on modular multiplicative inverse not existing for even members of (Z/2^nZ)*.

Thanks.

Answer 1

On a general basis, we don't want to encourage this kind of question:

• References to code are not good descriptions of cryptographic algorithms. Good descriptions use the language of mathematics, not programming.

• A description on a set of files on github is not permanent enough; if you ever change it, then this will make this question unreadable.

• There is a very inefficient and tiresome cycle, which goes thus: "Hey, I don't know the subject, but I have this idea; is it secure ? -- No, it is not, for this reason. -- What if I add a +1 there ? -- No, does not help. -- Then what if I also put a +2 at that place ? -- ..." Experience shows that this kind of process never ends up with a good algorithm; however, it produces long-winded awful discussions. It is already bad enough on Usenet groups like sci.crypt; on a Q&A site like this one, it will just not do.

From a cursory look at your files, though, it appears that you want to use Shamir's three-pass protocol. This requires a commutative cipher such that you can encrypt a message with key u, then with key v, and then decrypt with key u and v in that order, and get back the original message. Unfortunately, commutative ciphers are hard to make without a lot of mathematics, like modular exponentiations modulo big primes.

Your idea to do multiplications modulo 2ⁿ and to "encrypt" only message values x which are not invertible modulo 2ⁿ is not secure. Indeed, from the outside, the attacker sees x*u, x*v and x*u*v (all values modulo 2ⁿ). Since x is even, there are integers m and y such that y is odd and x = y*2^m. u and v being odd (that's necessary for them to be invertible), the observed values are necessarily multiple of 2^m and not 2^m+1. In other words, expressed in binary they all end with exactly m zeros.

The attacker's goal is to recover x. He already knows m, as explained above. He wants y, which has length n-m bits. By simply dividing all the values he observed by 2^m, he gets y*u, y*v and y*u*v, all values modulo 2^n-m, and they are all odd, hence invertible. It then suffices to compute (y*u)*(y*v)/(y*u*v) (modulo 2^n-m), which yields y. End game.

The above generalizes to all computations modulo some integer N when taking x to be non-invertible modulo N.

I encourage you to do your homework, i.e. read the Handbook of Applied Cryptography, which is a free download and very good reading (if a bit terse at times). Shamir's three-pass protocol is described in chapter 12, page 500. Mind the following passage:

While it might appear that any commutative cipher (i.e., cipher wherein the order of encryption and decryption is interchangeable) would suffice in place of modular exponentiation in Protocol 12.22, caution is advised. For example, use of the Vernam cipher (§1.5.4) would be totally insecure here, as the XOR of the three exchanged messages would equal the key itself.

The worst sin in scientific research is to disregard previous research.

Answer 2

I didn't have a chance to look at the link, but the fundamental problem with key distribution for one time pads is that they are purely random. Any attempt to encrypt them using a pattern results in an encryption that has less than perfect randomness and thus reduces the effectiveness of the OTP to that of the method of exchange. A one time pad is only as secure as it's distribution and provided that the OTP is truly random, it maintains the exact security of the key distribution method. The advantage being that you can check the security of the exchange prior to sending sensitive information.