Criticism of a proposed stream cipher requested.
in [Cryptography]
|
Prev: A simple scheme of combining PRNGs
Next: Criticism of a proposed floating point (cs)prng requested.
From: Keith F. Lynch on 4 Jun 2010 20:14 Mike Amling <mamling(a)rmcis.com> wrote: > Cryptoengineer wrote: >> The possible permutations are limitless. I actually forget what >> combination of these I use for my offsite backups, as I wrote the >> program some years ago. > Good luck doing a restore. Peter was quoting me. He was quoting a message which I had since superseded, as I've since explained my complete system both here and in the other newsgroup (rec.arts.sf.fandom). Anyhow, as long as I have the unencrypted source code, which I do on every backup, it wouldn't't matter whether I *had* forgotten how it works, so long as I remembered the key. -- Keith F. Lynch - http://keithlynch.net/ Please see http://keithlynch.net/email.html before emailing me.
From: Keith F. Lynch on 4 Jun 2010 21:05 Francois Grieu <fgrieu(a)gmail.com> wrote: > I'll assume that in the enumeration above, "Hash" is used where the > standard terminology is Exclusive OR. Yes, sorry. > I remark that if the plaintext is all-zeroes I never encrypt any files of all zeroes. Why would you think I would? I'll agree that you could get S, up to the length of the file, if I did. > This hypothesis can be easily tested and the key recovered using the > linearity-based attack proposed by Paul Rubin. Are you saying this attack would work even if the file isn't all zeroes? How? > From an academic standpoint, this is an attack (for an ideal cipher, > the ciphertext should never leak any information on the plaintext, > beside its length perhaps, and even known plaintext should not > reveal the key). I don't see how known plaintexts would reveal the key, except for unusual special cases such as all-zeroes. Or any plaintext that was written an alphabet of just one or two characters, since "stirring" doesn't alter such texts. > It is not clear is the same key (thus S) is reused for different > plaintexts; ... Yes, otherwise I wouldn't have bothered with stirring. It did occur to me to just use the stream cipher. I would have a different key for every file, and all the keys would be stored in an index which would be encrypted with a master key. I seem to recall that the main reason I didn't take that approach is that I couldn't find a way with the hardware I had to generate enough random keys. With the approach I took, since I only needed one (100-bit) key, it was practical to generate it by coin flipping. It's possible to flip coins fairly rapidly by placing a large number of identical fair coins in a can, shaking it vigorously for several seconds, then removing coins from it one at a time without looking at them until you've set them all down in a row. But 100 coins times the number of files I want to encrypt, that's not practical. > If the key is reused, it is enough for an adversary to manage to > inject one short all-zeroes file in the plaintext files to recover > the key and decipher all the other files. That can occur in real > life (you receive a number of interesting test cases and incorporate > them in your plaintext files, inclusing the rogue one). Not the way I do things. The only files I ever bother to encrypt, or even save, are ones I look at. If someone emails me a bunch of NULs, or any other kind of garbage, I won't be saving that email, much less encrypting it. >> One feature it has is that it's the same forwards and backwards: >> I don't have to specify whether I'm encrypting or decrypting. > In some contexts that property is a weakness. In particular, if the > adversary can inject a ciphertext as plaintext, the cipher is broken. Once again, that never happens. If I can't make sense of an email, newsgroup posting, or other text, I don't save it. (I have a text- only Internet account.) Anyhow, even if they did, it would be broken *only for that one file*. The bad guy finds a backup thumb drive of mine buried in the woods. He's intrigued by the encrypted file named bad_guy_don't_read_this. So he makes a copy of the encrypted version, and emails it to me? Even if I saved that gibberish email instead of discarding it, and even if I then encrypted it, the email headers on it would prevent the encryption from reversing the previous encryption. >> The plaintext is typically a compressed file of English ASCII text, >> compressed using either gzip or bzip2. > If that's taken into consideration, we are getting far from a > simple, analysable cipher. Yes, systematically compressing the > plaintext before encryption tends to increase security. I figured it would. (Even though, as Phil pointed out, the first few characters of the compressed file are known.) But that's not why I do it. I do it to save space. And to save the time it takes to do a backup. (I've been told it shouldn't take two hours to overwrite a four gig USB thumb drive. But for me it does.) >> Why did I design and write my own system? Mostly just for fun. >> But also because that way I know for an absolute fact that neither >> the algorithm nor the program that implements it has any secret >> back doors. > That "no backdoor" argument also applies if you implement a simple > standard cipher yourself (e.g. AES-CTR) which is probably easier to > implement than yours. That would guarantee there's no backdoor in the program, but not that there's no backdoor in the cipher itself. How do I know its author didn't design it with a backdoor? For that matter, how do I know someone didn't spend an enormous amount of time, years ago, figuring out a way to crack it? The more people use it, the more motivation there is to break it. The longer it's been in use, the more time people have had to try and crack it. >> Nor has anyone ever worked on breaking this cipher. > This does nothing to demonstrate that the cipher is secure; on > the contrary. Is it really possible to demonstrate that a cipher (other than a one-time pad) is secure? Or only that it's insecure? Or that nobody has yet broken it, at least nobody who wanted to reveal that they had done so? >> Nor is anyone ever likely to > Now that the cipher is on sci.crypt, that no longer stands :-) Perhaps. Is anyone here interested in trying it? If so, I'd be glad to provide some sample ciphertext. Just tell me how long the ciphertexts should be, how many of them there should be, and how many bits (if not a full 100) the key should have. And whether you'd prefer ASCII text, gzipped text, or bzip2ed text as the plaintext. No, I'm not going to provide a file of all NULs as a plaintext. :-) >> "Stirring" has some interesting mathematical properties. > Yes, but it is slow (256 operations per byte of plaintext for each > of the three stirring). It's enormously faster than actually making the backup, which just just a straightforward copy. (Well, okay, I'm cheating. I do a full backup of all files, old and new, every time, but don't re-encrypt all the encrypted files every time. But it's fast enough that there would be little benefit to making it faster.) -- Keith F. Lynch - http://keithlynch.net/ Please see http://keithlynch.net/email.html before emailing me.
From: Bryan on 5 Jun 2010 10:10 Mok-Kong Shen wrote: > schrieb Greg Rose: > > As usual, M-K fails to meaningfully contribute to the > > discussion. Please don't bother to try to educate him. > > If you could "explain" you point, then please "do" so. Otherwise > you are only doing exactly that yourself that you intend to > discredit me! Shen's analysis here is actually a lot worse than useless, assuming anyone were to take it seriously. No, a message-specific key does not mean that known-plaintext attacks do not apply. For example, lots of data formats make parts of the message predictable and thus give the attacker known plaintext. Shen's been around sci.crypt for over a decade, and we've been over this issue before. -- --Bryan
From: Keith F. Lynch on 5 Jun 2010 17:40 Bryan <bryanjugglercryptographer(a)yahoo.com> wrote: > No, a message-specific key does not mean that known-plaintext > attacks do not apply. For example, lots of data formats make > parts of the message predictable and thus give the attacker > known plaintext. In the case of my cipher, a known-plaintext attack does not apply, with the exception of a very few unlikely plaintexts such as all NULs or all DELs. It looks like the first four characters of every gzipped email file are the same. However, even if it was the first forty characters, this doesn't help, since my "stirring" steps ensure that the encrypted versions of those characters are distributed randomly through the encrypted file, in different places depending on the contents of the rest of the plaintext file. -- Keith F. Lynch - http://keithlynch.net/ Please see http://keithlynch.net/email.html before emailing me.
From: Maaartin on 5 Jun 2010 18:09
On Jun 5, 3:05 am, "Keith F. Lynch" <k...(a)KeithLynch.net> wrote: > Is it really possible to demonstrate that a cipher (other than a > one-time pad) is secure? Or only that it's insecure? Or that nobody > has yet broken it, at least nobody who wanted to reveal that they had > done so? For all good ciphers there are some proofs. Proving them secure is in fact impossible, but there are proofs showing them immune against known attacks. Even in case the NSA could crack AES, it wouldn't be cheap. I assume that the electricity bill for cracking my files would cost much more than they're worth, even assuming specialized hardware. On Jun 3, 5:09 am, "Keith F. Lynch" <k...(a)KeithLynch.net> wrote: > Why did I design and write my own system? Mostly just for fun. But > also because that way I know for an absolute fact that neither the > algorithm nor the program that implements it has any secret back > doors. Nor has anyone ever worked on breaking this cipher. Nor is > anyone ever likely to unless someone *really* wants to read my files, > which seems unlikely. If you're concerned with security and don't trust any program, you can implement a well-known algorithm yourself. If you don't trust any well- known algorithm, you can combine it with your own in a way assuring the result is at least as strong as any of them. Your algorithm is harder to implement and way slower than AES, so why not? On Jun 5, 11:40 pm, "Keith F. Lynch" <k...(a)KeithLynch.net> wrote: > In the case of my cipher, a known-plaintext attack does not apply, > with the exception of a very few unlikely plaintexts such as all NULs > or all DELs. Let me reformulate it: - You cipher was shown not to be usable as general purpose cipher. - It was shown to be vulnerable to chosen plaintext attack. - It wasn't shown to be vulnerable to known plaintext attack YET. |