[1808] in linux-security and linux-alert archive
[linux-security] Re: "Flavors of Security Through Obscurity"
daemon@ATHENA.MIT.EDU (Rogier Wolff)
Mon Jun 1 04:07:34 1998
To: linux-security@redhat.com
Date: Mon, 1 Jun 1998 09:49:19 +0200 (MET DST)
In-Reply-To: <98053011532200.04000@brandonppp> from "Brandon K. Matthews" at May 30, 98 11:44:39 am
From: R.E.Wolff@BitWizard.nl (Rogier Wolff)
Resent-From: linux-security@redhat.com
Reply-To: linux-security@redhat.com
Brandon K. Matthews wrote:
>
>
> This was posted not too long ago on sci.crypt... Enjoy... I think the most
> relevant information is near the top, but it's all quite good... :-)
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>
>
> There is no intrinsic difference between algorithm and data, the
> same information can be viewed as data in one context and as
> algorithm in another. Why then do so many people claim that
> encryption algorithms should be made public and only the key
> should be kept secret? (This is the famous and derisive mantra
> about "security through obscurity".) There are several answers:
> a) Some people, with little understanding about computer
> technology, try to keep secret what their programs do, even
> though the programs themselves are public. A program *is* a
> representation of the algorithm, even though it happens to be
> more difficult for humans to read than, say, an detailed
> description in English. Actually it is a very good idea to keep
> secret the algorithm (in all its representations), as long as you
> can afford to do so. That is why major governments do exactly
> that.
>
> b) One can memorize a key and keep it secret in one's head.
> Normally, encryption algorithms are too complicated to be
> memorized. Therefore it is easier to keep secret a key than an
> algorithm.
> c) Most people and organizations do not have sufficient expertise
> to create a new and good encryption algorithm and then try to
> keep it secret. A bad encryption algorithm, in this context, is
> an algorithm that can be broken by a sophisticated attacker even
> without knowledge about the algorithm itself.
This is a VERY important one.
> As you see, the reasons are of a practical nature, and are not
> derived from any fundamentals in cryptology. If we could find a
> practical way to keep secret both the key (that is the data the
> encryption method operates on) and also the method itself (or at
> least part of the method), then security would be greatly
> enhanced because the attacker would have less knowledge to work
> with.
The problem is: What attacks do you want your cryptography to be
"secure" against?
- unknown plaintext, unknown algorithm.
- unknown plaintext.
- known plaintext.
- chosen plaintext.
- chosen key.
Most Cryptographic algorithm designers want their algorithm to resist
all of the above.
You want the algorithm to resist even the hardest attack (the attacker
can "borrow" your box to do some sample encryptions. At first this
sounds pretty odd that you'd allow an attacker to borrow your
encryption box. However consider an ATM. When I can listen to its
communications, I see a message coming by which I KNOW must say: "I
have a Mr. Wolff here, his PIN is xyzw, can he withdraw $200?" Now, I
personally don't know how they would put the bits in this sentence
into the plaintext message, but the algorithm must resist aginst
this type of attack.)
> I believe there are several ways to overcome these practical
> difficulties:
>
> a) Machine generated secret ciphers.
>
> Today there are only a few encryption algorithms that are
> generally accepted as good. But suppose there existed a generator
> program which could construct a new encryption algorithm
> depending on some random input. Actually, the generator program
> would produce another program which would then be used as the
> encryption software. In some important cases, it is feasible to
> keep secret the resulting program: International organizations
> could distribute disks containing the program using trusted
> persons, the program could be loaded in centralized servers which
> actually operate from within a safe, or maybe the program (in
> encrypted form) would be run only from a floppy disk which would
> be handled with the same care as the key to a safe. We all know
> that absolute security is impossible. What I am suggesting here
> is that in many cases this system of security is better than one
> using a standardized and public algorithm which attracts a lot
> cryptanalytic work and may be broken in the near future or may
> have already been broken in secret.
If you have the "generator program", then there is just a few bits
more of "key" that need to be "known" to decypher a message. This is
nothing different from a slightly more complex encryption algorithm
and a slightly larger key.
> b) Intrinsically secret ciphers.
>
> Extend secrecy to parts of the encryption method. In his book,
> Schneier very briefly describes a variant of DES where the Sboxes
> (which most people would consider as part of the algorithm) are
> variable and depend on the key. Another very interesting
> possibility would have the key express the encryption method. In
> other words consider the key as the program, and the cipher
> simply as an interpreter, that follows the key's instructions to
> scramble the plaintext or unscramble the ciphertext. This would
> call for large keys, but not larger than keys used in public key
> encryption.
If you randomly chose S-boxes, the resulting cypher is very
weak. IBM/NSA seem to have done a remarkable job at finding those
S-boxes that result in a good cypher. This is the consensus
about DES among the cryptanalysts nowadays.
If you start modifying your S-boxes along the road, depending on your
key, all you can do is effectively create a larger key. This is
nothing different from a slightly more complex encryption algorithm
and a slightly larger key.
> c) "Variable" ciphers.
>
> The idea here is to implement a cipher that incorporates a huge
> number of different encryption functions. The objective is to
> overwhelm the analytic capability of an attacker. (At the end of
> this post you will find the outline of a proof about why a cipher
> of this type is intrinsically more secure.)
The word "overwhelm" is misplaced.
> My GodSave encryption algorithm belongs to this class of
> "variable" ciphers. It extensively uses data of the key to change
> the control flow of the program execution. In other words,
> whereas most algorithms just operate on the key, GodSave uses
> information in the key to decide how to operate. Even better: It
> is constructed in such a way that large sections of its code can
> be modified by a programmer without affecting the security of the
> algorithm, offering some of the advantages described under a)
> above.
Not true. Suppose my application is "hurt" by even a small amount of
plaintext seeping through. ("The winning lottery numbers are: 1, 23,
26, 34, ..." Someone being able to decrypt part of this message before
the results are published, some part of the numbers, can greatly
increase his chances of winning. Bad for the lottery.)
Now if my "modifications" make every 8th block of 64 bits trivially
decryptable, then I stand a chance of "publishing" an important part
of the plaintext.
> Here is the definition of another cipher of this type (let us
> call it "heavy DES"): Start by randomly defining 16K DES keys;
> you need less the 1 MB space in your hard disk to save them.
> Suppose that this large key set is public (either by choice or
> because an attacker gained access to your computer and stole it).
> So now you have a large set of DES ciphers with *known* keys; the
> effort to break any one of them is 1. Now define a secret key of
> 140 bits. Use 14 bits at a time to index one of the 16K DES
> functions. Encrypt a 64 bit block by sequentially chaining the 10
> indexed DES functions. DES is not a group, therefore each
> instance of the 140 bits long key results in a different mapping
> of the plaintext space into the ciphertext space. If we choose
> from 2^N DES functions and chain P of them together (in the
> example above N=14 and P=10) then there are 2^(N*P) different
> instances. Already with 140 bits of entropy, a brute force attack
> is out of the question no matter how many hardware coded DES
> machines you have. Suppose you have perfect cryptanalytic
> knowledge of DES - trapdoor and all - even then, can you see a way
> to attack this variable version?
Yes. Suppose I have a perfect cryptanalytic knowledge of DES: Suppose
I instantly know the plaintext given a cyphertext. In that case the
cryptographic function could just as well be the identity function.
So, now I have a cyphertext. That's the output of your 10th DES
step. Because we simplified DES to the identity function, that's
also the input to the tenth step, the output of the 9th step......
Also the plaintext.
Suppose, that from the output of DES, I can deduce which of your 16K
DES keys was used to generate it. The DES keys are known in this case,
and DES wasn't designed to resist "known key" attacks. But I cannot do
this perfectly. I always get two "possible key" alerts. So, from your
cyphertext, I can reverse two possible "level 9" outputs. From that I
get four level 8 outputs etc etc. In total just 2^20 possibilities to
check, and Bingo.
[.....]
> 2^(N*k)+0.5*2^(N*k)=3/2 * 2^(N*k). Therefore you need more effort
> to break C with a key of N+1 bits, than either A or B with a key
[.....]
Next we see lots of mathematical sounding stuff, that is totally
irrelevant.
Your described "multi-DES" is essentially an ECB cypher (Electronic
Code Book). This suffers from all the weaknesses of ECB cyphers.
Suppose the ATMs used this. Suppose the bank sends:
" Transaction approved, please pay mr XYZ: $0000200,00 "
Now if I can change that 00002 into 20000, I'm suddenly rich. ECB
means that I can watch someone withdraw $2000000,00, and insert part
of that message into the stream.
You imply that I can generate cyphers of arbitrary key length. That is
not true: There are only (2^64)! ECB cyphers. Now this is quite a lot,
but that's a certain hard upper limit. Suppose that instead of passing
64 bits at a time into the DES engines, I pass in just 8. (Say that I
want to be able to encrypt a "telnet session", where characters don't
come in 8 at a time...). Now the number of ECB codes is simply 256!,
which is not longer than 8*256 bits. You imply that I could generate
longer keys than this.
The important thing is, that in cryptography, all college students at
one time or another think they've found a wonderfully secure new
cryptographic algorithm. Experience shows that so far all of them have
had serious flaws.
Leave designing cryptographic algorithms to the experts. Allow
everybody to know the algorithm. The bad guys will steal a "box"
anyway. Keep your keys secret, but that's the only thing you should
keep secret. Make sure that your algorithm is resistant to known
plaintext attacks, and all "known ..." variants.
If you keep your algorithm secret, most likely some highschool kid
will eventually figure out a fast way of decrypting your cypher. The
advantages of publishing the algorithm are twofold. You get to know
from the beginning that the cryptanalyst will be working with a
known-algorithm: you won't be fooled into thinking that he can't
figure out the algorithm. And everybody else gets to shoot holes in
it.
As a reference, read the chapter on random numbers (a good random
number generator can serve as a cryptographic engine) in "the art of
computer programming" by Donald Knuth, published 1972 (or
thereabouts). The main point being that having the control flow change
depending on the data is NOT a good way to make a flawed algorithm
better. A good algorithm is the only solution.
Regards,
Roger.
P.S. Future posts with "I've designed this fancy cryptographic
algorithm" will be ignored...
--
If it's there and you can see it, it's REAL |___R.E.Wolff@BitWizard.nl |
If it's there and you can't see it, it's TRANSPARENT | Tel: +31-15-2137555 |
If it's not there and you can see it, it's VIRTUAL |__FAX:_+31-15-2138217 |
If it's not there and you can't see it, it's GONE! -- Roy Wilks, 1983 |_____|
--
----------------------------------------------------------------------
Please refer to the information about this list as well as general
information about Linux security at http://www.aoy.com/Linux/Security.
----------------------------------------------------------------------
To unsubscribe:
mail -s unsubscribe linux-security-request@redhat.com < /dev/null
