Re: Ecryption Cracking Tools

[Fred Cohen <fred.cohen () all net>]

I make it up as I go along...

The problem is that for any decent cipher, the likelihood of any  
given bit of the output being 1 or 0 is 50% (or some pre-defined  
known percentage in the more general case - but assume 50% of ease of  
analysis). So for each output bit, there is a 50% chance of 1 or 0 in  
each of two different schemes. The goal of two different valid  
decrypts - one easier and the other harder to obtain - requires that  
they encrypt two different messages to the same output message. Seems  
to me like the size of the search space for finding a valid and  
convincing input message under a key for the simpler system to match  
the more complex system is 1 in 2^n where N is the length of the  
ciphertext of the harder cipher's output. In other words, exponential  
in the size of the output. That assumes, of course, that you want one  
of the ciphers to be strong and that there is in fact a match to some  
text for the second cipher.

Now of course the Vernam cipher (which is perfect in theory) can  
transform any text into any output if you apply the right key, but  
for things that use a finite sized key smaller than the message by at  
least the unicity distance, the problem will become severe because  
the match for each block (assuming a block cipher) will have to pick  
one message out of the size of the key space that fits into each  
block of the encrypted original cipher text. The key cannot change  
from block to block or you have a Vernam cipher again and serious  
practicality problems in key distribution. So if the tough cipher is  
128 bytes of key and the easy one is 64 bytes of key, we need to find  
2 plaintexts that are reasonable for format and that, under the same  
64 byte key, match the cipher text of the longer key. Assuming a  
symetric key system (encrypt and decrypt are the same, we can take  
the ciphertext and decrypt each block for each key in the smaller  
keyspace and see if we get a reasonable syntax plaintext. If we do,  
for the firs 64 bytes we try for the next 64 bytes, etc. If we ever  
encounter a decrypt that is not valid input syntax we need to try the  
next key. If the unicity distance for the valid syntax of the inputs  
is 2.4 (like English) we have a 1 in 2.4 chance that any random  
output from decryption is a valid input. That, of course, assumes  
that the validity is character by character only. If the syntax that  
is valid is something like meaningful English sentences, then we are  
in big trouble. The portion of the totality of the space of bytes  
that comprise valid English sentences is quite small, so the odds of  
hitting one are also very small. However, if we use a limited syntax  
it helps.

So then, to finish up, after N uses of the easier key, the odds will  
be 1 in unicity distance (u) to the power N. For a 64 byte key (easy)  
after 1K of message at unicity distance 2, we will have a 1 in 2^16  
likelihood of a valid syntax match for any given key. This can only  
go on so long of course because after the message length reaches the  
length of the smaller key squared, the odds of success get to where  
the total key space is unlikely to have even one match. And of course  
unicity distance 2 for full text requires compression way beyond what  
is achievable for normal languages in binary representation. But if  
we use 6-bit with compression and a simplified language, we might be  
able to do exhaustion of the key space of a simple and short cipher  
and get valid syntax back out from whatever the real message is as  
long as the syntax is atypical and the total volume sent is small  
enough.

FC

On Oct 27, 2005, at 3:24 PM, Austin Murkland wrote:

> Well i understand it would be difficult...just not how difficult or  
> if it would be impossible...any suggestions on source material i  
> could brush up on to get a better idea of how to develop such a thing?
>
> -Austin Murkland
>
> Fred Cohen wrote:
>
> > Alas it is far harder than it might seem. Shannon tells us that  
> > the unicity distance is only 2.4 times the key size for English  
> > and attempts to create multiple valid looking decryptions for  
> > multiples of that is very hard. A better approach is to provide  
> > lots of excess data so that parts can be decrypted with different  
> > approaches, but this is also problematic in its way. Another  
> > approach is what I used in DTK (Deception ToolKit). We created  
> > false password files that could be cracked and used them to tell  
> > how good the attackers were based on how long it took them to  
> > break what.
> >
> > FC
> >
> > On Oct 26, 2005, at 11:54 AM, Austin Murkland wrote:
> >
> >
> > > I had a thought.  With all the talk of honeypot systems, and  
> > > services.  Wouldn't it make more sense to have a Crypto cipher  
> > > that took into account the possibility of being brute forced and  
> > > provided one or more sets of logical pseudo-information when  
> > > cracked, but only the real information when actually cracked/ 
> > > authenticated?
> > >
> > > at it's simplest level, have one set of data that is the actual  
> > > message, and another set of data that is something that could be  
> > > the actual message.  Security would increase given the number of  
> > > sets of pseudo-data included in the encrypted message...so if it  
> > > were cracked using brute force, how would they know it was  
> > > actually what they were looking for.  My understanding is that  
> > > brute force relies on there being only one possible true answer  
> > > for it to work.  While this is still true with this idea, there  
> > > also exists multiple pseudo-answers that provide information that  
> > > may or may not look like the actual answer.
> > > This could be combined with further honeypot systems and ids to  
> > > both make it difficult to get to the correct system, and to  
> > > immediately be notified that someone is actively trying to brute  
> > > force your encryption and it's time to change keys.  E.g. a  
> > > password is encrypted using this method, and 30 sets of pseudo- 
> > > data is included in the encrypted password.  lets say when  
> > > properly brute forced it provides 20 deadend passwords that just  
> > > don't work, 10 passwords that lead to honeypots systems, and 1  
> > > real password that gets them, or the authenticated user in.  if  
> > > they try any of the 30, before the 1, an IDS could be easily  
> > > configured to ban their IP, alert the admin, or even run a script  
> > > that does all this and then changes the key.
> > >
> > > i don't know if this is a new idea or not.. i guess it would be  
> > > HoneyPot Encryption... ?
> > >
> > > Austin Murkland
> > >
> > > john () gmail com wrote:
> > >
> > >
> > > > Use a Vernam cipher. If you do it right it will be fun to watch  
> > > > them try to crack it.
> >
> > -- This communication is confidential to the parties it is  
> > intended to serve --
> > Security Posture            securityposture.com          tel/fax
> > University of New Haven               unhca.com        925-454-0171
> > Fred Cohen & Associates                 all.net      572 Leona Drive
> > Security Management Partners    policygeeks.com    Livermore, CA  
> > 94550

-- This communication is confidential to the parties it is intended  
to serve --
Security Posture            securityposture.com          tel/fax
University of New Haven               unhca.com        925-454-0171
Fred Cohen & Associates                 all.net      572 Leona Drive
Security Management Partners    policygeeks.com    Livermore, CA 94550