6
$\begingroup$

In the comments of the question "Why programming languages don't provide simple encryption methods?" the following statement was made:

A well thought out, tested and understood standard that has undergone extensive review by the crypto community has a much better [chance] of avoiding compromise than a system designed by a single engineer using a fairly low level library.

to me such a system would have the following requirements:

  • Encryption would require nothing more than a string of text to encrypt and an easily programmatic producible "key".
  • Decryption would require nothing more than an easily programmatic producible "key".
  • The result would not ever be able to be determined with out access to the key even given a reasonably huge finite (IE more than we can ever expect to have available) amount of computing power.
  • No method of attack would ever trivialize the determining the key or the source text used for the encryption.

My opinion is that the nature of encryption is that it is impossible for a standard like this to work given an infinite amount of computing power. We may be able to do this for the computing power of today but eventually given enough power it will be trivial to decrypt any scheme if we know how the scheme works and it only requires a single key. Is such a scheme possible?

Improve this question
$\endgroup$
7
  • $\begingroup$ I agree with your analysis that given infinite computational resources such a scheme, outside of a OTP, would likely be compromised. Generally success of a crypto-system is defined by showing that the best possible attack is brute forcing the key-space. I think the more interesting question is if such a scheme is possible given key-space bounded compute time (a more typical definition of security). The most interesting question, to me, is how can we increase our trust in crypto-systems given that non-cryptographically trained engineers will be (mis)using them (fool proof security). $\endgroup$
    – Ethan Heilman
    Jan 6, 2012 at 20:10
  • $\begingroup$ @EthanHeilman - The problem is computing power is continually increasing and new processor types like GPU's create new functionality that basically trivializes some encryption cracking. So any standard and secure encryption that could be built in would need to be able to withstand brute force. $\endgroup$
    – Chad
    Jan 6, 2012 at 20:54
  • $\begingroup$ I think we can set the bar pretty high in terms of brute force. No one is concerned that AES will be broken due to brute forcing the key. In fact it is quite easy to create a crypto-system with a key so large a computer the size of the universe couldn't brute force it. For instance using all the atoms in the universe ($10^82$ atoms) as computers capable of computing 1 trillion keys a second, one could brute force roughly 2^314 keys a second. To brute force a 512-bit key would take roughly $10^{52}$ years (far far longer than the lifetime of the universe). $\endgroup$
    – Ethan Heilman
    Jan 6, 2012 at 21:23
  • $\begingroup$ @EthanHeilman - I am confused you indicated that the Rijndael was too complex to be considered simple in the other thread. $\endgroup$
    – Chad
    Jan 6, 2012 at 21:31
  • $\begingroup$ I have no problem with Rijndael (AES) per se, what I have a problem with is that the library is expecting the engineer to turn a secure block-cipher (AES) into a secure crypto-system (AES is fine but it needs all the other stuff: padding, authentication, IV generation, a chaining mode). The default crypto libraries that an engineer encounters should operate at the level of crypto-systems not at the level of primitives. For example bcrypt does a decent job of this with hashing passwords (with some reservations). The default interface is BCrypt::Engine.hash_secret(password, password_salt). $\endgroup$
    – Ethan Heilman
    Jan 6, 2012 at 21:42

2 Answers 2

Reset to default
11
$\begingroup$

If the key is:

  • generated with an unpredictable truly random uniform generator (not a pseudo-random generator);
  • as long as the data to encrypt;
  • used for only one message ever;

then this is the One-Time Pad model, and you can encrypt data by a simple bitwise XOR (no need for an explicit function, just XOR).

Otherwise, there is no solution which resists attackers with infinite computational abilities. Shannon's thesis is all about that.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Basically, if there is sufficient information in the ciphertext, then an attacker can break it. If there is insufficient information, then no. For example, I picked a number from 1 to 10 and encrypted it by adding a key (from 0 to 100) to it. I got 41. You have infinite computing power. What number did I pick? $\endgroup$
    – David Schwartz
    Jan 9, 2012 at 23:37
  • 1
    $\begingroup$ @DavidSchwartz - Maybe not but I know your key was between 0 and 41... and I know that the encrypted number was <= 42. I have reduced the pool of potentials by ~59% $\endgroup$
    – Chad
    Jan 10, 2012 at 13:53
  • $\begingroup$ Two words: Vernam Cipher $\endgroup$
    – user1364
    Jan 11, 2012 at 20:09
3
$\begingroup$

Is such a scheme possible?

Theoretically "Yes", but only under a certain, single condition...

It is a common misconception that every encryption method can be broken. In connection with his WWII work at Bell Labs, Claude Shannon proved that the one-time pad cipher is unbreakable, provided the key material is

  1. truly random,
  2. never reused,
  3. kept secret from all possible attackers,
  4. and of equal or greater length than the message.

Most ciphers, apart from the "one-time-pad", can be broken with enough computational effort by brute force attack, but the amount of effort needed may be exponentially dependent on the key size, as compared to the effort needed to make use of the cipher.

In such cases, effective security could be achieved if it is proven that the effort required (example: the "work factor", as Claude Shannon defines it) is beyond the ability of any adversary. This means it must be shown that no efficient method (as opposed to the time-consuming brute force method) can be found to break the cipher.

As no such proof has been found to date related to a "one-time-pad", the "one-time-pad" remains the only theoretically unbreakable cipher.

Read again: ...theoretically unbreakable...

UPDATE

As this came up in the comments... when it comes to creating a one-time pad, there are several hardware solutions and software implementations that would satisfy the "truly random one-time pad" definition. Some initial info can be found at http://en.wikipedia.org/wiki/One-time_pad#True_randomness , but if you really want to dive into this a bit more, you'll probably want to check on "Randomness Recommendations for Security", which is available at http://www.ietf.org/rfc/rfc1750.txt

Oh, and while I'm updating my answer: the (as OP calls it) "scheme" we're talking about is commonly known as Vernam Cipher, just in case you want to cross-check my answer using search engines. ;)

RC4 is an example of a Vernam cipher that is widely used on the Internet.

More information about the Vernam Cipher, it's history, it's inventor and related patents can be found at http://en.wikipedia.org/wiki/Gilbert_Vernam

Improve this answer
$\endgroup$
13
  • $\begingroup$ Actually, there's an infinite set of ciphers that are cannot be broken, but they all share the 4 points you list. Trivially, for any bijective function f, f(OTP(x)) is such a cipher. $\endgroup$
    – MSalters
    Jan 9, 2012 at 14:07
  • $\begingroup$ I agree with your answer but am not able to accept it because we do not have a method to generate a true random one time pad in a computer program. $\endgroup$
    – Chad
    Jan 9, 2012 at 14:25
  • $\begingroup$ @Chad : to accept an answer, you need to click the "checkmark" next to the answer. ;) $\endgroup$
    – user1364
    Jan 10, 2012 at 0:13
  • $\begingroup$ @e-sushi I know how to accept it. I am saying that this does not really meet the criteria since we can not programmatically generate a truly random one time pad. $\endgroup$
    – Chad
    Jan 10, 2012 at 13:43
  • $\begingroup$ @Chad : of course you can. But you're correct that "ye average programming language" will not satisfy as they mostly use pseudo-randomizers. Yet, using the correct means, it can be done. Remember that a random pad can be generated from any piece of random data. In fact, you could even grab random data by fetching cloud movements from satellite images. On a more "regular" level, there are hardware random number generators and other things. Check the update in my answer. $\endgroup$
    – user1364
    Jan 11, 2012 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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