CDR: Re: "ChronoCryption" algorithm - $50 reward for spotting a flaw
Ray Dillinger writes:
In the interest of making some news if you don't like the news you're getting, I present -- the Country Mile Cipher. Algorithm details available (for now) on
http://www.sonic.net/~bear/crypto/countrymile.html
This is a stream cipher based on the Blum-Blum-Shub pseuodo- random number generator -- and on work done more recently by Ronald Rivest, who "digitally sealed" a message that he expects to take 30 years of continuous computing to unscramble.
Your idea is to take BBS as a stream cipher, use a value based on a secret short key as a starting point, and then cycle it potentially a whole lot, millions or billions of cycles or more, before beginning to cipher the message with it. Using the idea of Rivest et all you can cycle BBS forward arbitrarily far in a limited amount of work, if you know the modulus factors. So you can encrypt with little work, while making the decryptor do an arbitrary amount of work even if he knows the key. You've combined the idea of time lock crypto with an encryption function. It's not clear these two ideas go all that well together, like the SNL product that was both a floor wax and a dessert topping. Usually you either want to encrypt, in which case you want to make it easy to decrypt for the guy who knows the key, or you want to time-lock, in which case you want to control how hard it will be to find the key. There don't seem to be that many cases where you want to allow decryption but only if you both know the key and are willing to put in a lot of time. Even if you did want to do that, you could just use Rivest's time lock to hide a key which then gets combined with your short key to produce the actual key to the message. Along these lines your own idea could be simplified; don't encipher the whole message using BBS, just encipher a block-cipher key and use 3DES or similar to encipher the message. You might also want to take a look at the paper by Dan Boneh and Moni Naor from Crypto 2000, http://crypto.stanford.edu/~dabo/abstracts/timedcommit.html. They have a similar idea but came up with an application for it in fair contract signing (where one party should not end up with the signature on a contract unless the other party does too). For their application they need to be able to encrypt a message such that it can only be decrypted with a specified large amount of work. However they must be able to reveal the encrypted message and prove that the decryption was accurate, using a small amount of work. This could be done in your scheme simply by revealing the modulus factors (the "long key") but they want to reuse the modulus so they use some fancy zero knowledge proofs.
Your message has been rejected and is being returned because it appears to be a reply to an alias that is designed for one-way communication only. You should reply only to the sender of a message sent to one-way aliases. If you wish to complain about abuse of a one-way alias, you should send E-mail to the postmaster of your domain. For example, postmaster@Eng. If your E-mail was addressed to more than one alias protected by this filter then you will get a copy of this message for each protected alias. Thank you for your cooperation and consideration, -- Postmaster P.S. This is an automatically generated message. -----------------Begin Returned Message------------------- Your message has been rejected and is being returned because it appears to be a reply to an alias that is designed for one-way communication only. You should reply only to the sender of a message sent to one-way aliases. If you wish to complain about abuse of a one-way alias, you should send E-mail to the postmaster of your domain. For example, postmaster@Eng. If your E-mail was addressed to more than one alias protected by this filter then you will get a copy of this message for each protected alias. Thank you for your cooperation and consideration, -- Postmaster P.S. This is an automatically generated message. -----------------Begin Returned Message------------------- Your message has been rejected and is being returned because it appears to be a reply to an alias that is designed for one-way communication only. You should reply only to the sender of a message sent to one-way aliases. If you wish to complain about abuse of a one-way alias, you should send E-mail to the postmaster of your domain. For example, postmaster@Eng. If your E-mail was addressed to more than one alias protected by this filter then you will get a copy of this message for each protected alias. Thank you for your cooperation and consideration, -- Postmaster P.S. This is an automatically generated message. -----------------Begin Returned Message------------------- Your message has been rejected and is being returned because it appears to be a reply to an alias that is designed for one-way communication only. You should reply only to the sender of a message sent to one-way aliases. If you wish to complain about abuse of a one-way alias, you should send E-mail to the postmaster of your domain. For example, postmaster@Eng. If your E-mail was addressed to more than one alias protected by this filter then you will get a copy of this message for each protected alias. Thank you for your cooperation and consideration, -- Postmaster P.S. This is an automatically generated message. -----------------Begin Returned Message------------------- Your message has been rejected and is being returned because it appears to be a reply to an alias that is designed for one-way communication only. You should reply only to the sender of a message sent to one-way aliases. If you wish to complain about abuse of a one-way alias, you should send E-mail to the postmaster of your domain. For example, postmaster@Eng. If your E-mail was addressed to more than one alias protected by this filter then you will get a copy of this message for each protected alias. Thank you for your cooperation and consideration, -- Postmaster P.S. This is an automatically generated message. -----------------Begin Returned Message------------------- On 5 Sep 2000, lcs Mixmaster Remailer wrote:
Ray Dillinger writes:
In the interest of making some news if you don't like the news you're getting, I present -- the Country Mile Cipher. Algorithm details available (for now) on
Your idea is to take BBS as a stream cipher, use a value based on a secret short key as a starting point, and then cycle it potentially a whole lot, millions or billions of cycles or more, before beginning to cipher the message with it. <...> You've combined the idea of time lock crypto with an encryption function.
Bingo.
It's not clear these two ideas go all that well together, <,,,> Usually you either want to encrypt, in which case you want to make it easy to decrypt for the guy who knows the key, or you want to time-lock, in which case you want to control how hard it will be to find the key. There don't seem to be that many cases where you want to allow decryption but only if you both know the key and are willing to put in a lot of time.
True. Not many. But, I think, some. It's a matter of using the right tool for the right job. The world doesn't need yet another cipher, because the ciphers we have are adequately secure and efficient. It doesn't need another timelock, because Rivest's does that job quite nicely. But I think Country Mile fills a niche that I don't think I've seen anything else fill -- a keyed timelock.
Even if you did want to do that, you could just use Rivest's time lock to hide a key which then gets combined with your short key to produce the actual key to the message.
Yes, and no. One application for Country Mile is for situations where you are restricted to a short key and want to get adequate security. By putting a two-second delay into the decryption function, which is almost nonexistent in human time to someone who has the key, you can make a brute-force attack on the key take thousands of times longer -- enough to make a 56-bit key, if not secure, then at least adequate for a few weeks of security. If you just used Country Mile to encrypt the key of another cipher system, then the effective brute force attack against that system could proceed without the country mile timelock slowing it down at all. 'Cause the system will always be attacked at its weakest link. It's true that this is an artificial and arbitrary restriction, caused mainly by legal boogerheads. But it's nice to have a tool in your box that can give you reasonable security anyway.
Along these lines your own idea could be simplified; don't encipher the whole message using BBS, just encipher a block-cipher key and use 3DES or similar to encipher the message.
Right. That's the way RSA is usually used. The fact doesn't affect the description of RSA, nor of Country Mile. Whether someone uses it that way is mainly a matter of what he or she wants to accomplish. But before deciding whether to use it that way, I hope he or she understands my comments about short keys and brute force attacks above.
They have a similar idea but came up with an application for it in fair contract signing (where one party should not end up with the signature on a contract unless the other party does too). For their application they need to be able to encrypt a message such that it can only be decrypted with a specified large amount of work. However they must be able to reveal the encrypted message and prove that the decryption was accurate, using a small amount of work. This could be done in your scheme simply by revealing the modulus factors (the "long key") but they want to reuse the modulus so they use some fancy zero knowledge proofs.
Right. Someone from sci.crypt has pointed out that the BBS modulus, which gets tranmitted with the ciphertext in Country Mile, constitutes a handy, and potentially large, subliminal channel. Which is another interesting feature, but not a viable attack on the cipher. Revealing the modulus factors in Country Mile would only de-timelock the one message encrypted under that modulus -- a fact which might turn out to be an important and desirable property in some protocols. Since new factors are chosen with each encryption, it doesn't suffer from the usual problem with stream ciphers, where you can't use the same key more than once. In fact you can go on using the same short key, with a different modulus, even after you "de-timelock" a message by revealing the modulus factors. Thanks for looking at it! Ray
participants (2)
-
lcs Mixmaster Remailer -
postmaster＠engmail2.Eng.Sun.COM