0

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.

  • @AJHenderson Cryptanalysis of a homemade scheme? No. – Gilles Aug 13 '13 at 22:52
  • Hello there Dave – Lucas Kauffman Aug 14 '13 at 7:52
5

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 2n and to "encrypt" only message values x which are not invertible modulo 2n is not secure. Indeed, from the outside, the attacker sees x*u, x*v and x*u*v (all values modulo 2n). Since x is even, there are integers m and y such that y is odd and x = y*2m. u and v being odd (that's necessary for them to be invertible), the observed values are necessarily multiple of 2m and not 2m+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 2m, he gets y*u, y*v and y*u*v, all values modulo 2n-m, and they are all odd, hence invertible. It then suffices to compute (y*u)*(y*v)/(y*u*v) (modulo 2n-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.

  • HAC looks like a good read. I see that it was written in 1996 - does that mean it is "old" in the sense that some of it will be out of date? If I read it, will what I learn be out of date? Or does this stuff in general develop slowly enough that it's still relevant? – loneboat Aug 19 '13 at 22:08
  • 1
    95% of the HAC is still up-to-date (note that the last edition is from 2001); and knowing what is in the HAC is necessary to understand the stuff which has been discovered or invented in the last decade anyway. – Thomas Pornin Aug 20 '13 at 0:38
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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.