# Maximum PC

 It is currently Mon Apr 27, 2015 12:05 am

 All times are UTC - 8 hours

 Page 2 of 2 [ 29 posts ] Go to page Previous  1, 2
 Print view Previous topic | Next topic
Author Message
 Post subject: Posted: Sat Jul 03, 2004 6:54 am
 I'd rather be modding!

Joined: Fri Jun 25, 2004 3:47 pm
Posts: 3731
Location: Las Vegas
Let's redifine things a little:

the password is what the user needs to know to decrypt the message
the key may, or may not, be the same as the password, but it is also needed to decipher the msg.
the rand, short for random, is the information about which cipher was used to initially encipher the plaintext

The key would not be the same as the password (unless someone was lucky). Its generated as a track on what the algorythm did randomly.

Quote:

Let's start with the second method you suggested - it is easier to attack.

In order for someone to decipher the message, they need to have the encrypted message, the password, and the rand (actually, they don't need to 'know' the rand - the information concerning the rand is just passed to them - I'll discuss not knowing the rand later). So where do we put the rand? It can't go in the password - the rand is random! It has to be located within the encrypted message.

well, I was thinking the key stays local - but I guess you could use the password algorythm to hide it in the text.

Quote:
So where do we put the rand. We can't do something obvious like encrypting the rand with some known cipher and putting it at the front or end of the message. It would be easy for someone to reverse engineer their own message and find the location. After they figured out which cipher is used to encrypt the rand, you're back to using just a single cipher. Worse yet, they may now know the key!

without the password, the key (or rand) is of little use - however, if the key is kept in the file - and it is placed based on the password - then one could eventually figure it out (if they had the algorythm).
Quote:
Don't waste neurons thinking about it though. We don't need transmit the rand. Since we have the password/key, we just go through the first decryption algorithm and then use that result and try each of the 100 remaining possible ciphers. On average, it will take 50 tries to get it. No biggie - computers are fast at this. A good marketing guy will spin doctor this and have people thinking the extra time is just making their data more secure. This is much better then trying to transmit the encrypted rand (at least of the possibilities that I considered).

You lost me there - you have to have the key. Otherwise, when you try to decypher you will run through the 100 possible decyphers - but you will not know which one was the right one.

Like this...

ABCD

rand cypher 1 (oct, no scramble)
101102103104

rand cypher 2 (convert to hex-20 unsing 2 decimals, no scamble)
01"0Q\$

Now, I didn't scamble the cypherbets 'cuz of time - but if I had, how would you know you broke the first cipher and could move on to the second?

Quote:
We could even take this a step further and disregard the rand in your first example. If we had 5 weak ciphers and randomly enciphered the plaintext 3 times with any of the ciphers, we would have a 5^3 combinations of ciphers. 125 is within working range, if you know the key, and it might be possible to use an alpha-beta algorithm to reduce the problem space further.

This technique of enciphering a message multiple time doesn't always improve things though. For example, some ciphers don't provide any extra security when they're used multiple times. You could use a Caesar shift, monoalphabetic substitution or transposition cipher on a message a 1000 times an it wouldn't make a bit of difference. The original weakness just shines right through. Occassionaly, it makes things worse. If anything, I suspect these techniques buy a little more time and help foil automated attacks.

True enough - if you use the same shift (or even a different one) everytime, you are doing nothing. But look above - this isn't like that. I dropped 4 letters into 12 numbers back to 6 characters. Had I used transposition - and a different one for both - things get complicated. You could even have a method designed for frequency breaks by adding false characrters at a (seemingly) random interval.

Manta

Top

 Post subject: Posted: Sat Jul 03, 2004 7:31 am
 I'd rather be modding!

Joined: Fri Jun 25, 2004 3:47 pm
Posts: 3731
Location: Las Vegas
Take the words that were solved for (falsely) out of Colby's post and run the program again.

Manta

Top

 Post subject: Posted: Sat Jul 03, 2004 1:45 pm
 Bitchin' Fast 3D Z8000*

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
MantaBase wrote:
Don't waste neurons thinking about it though. We don't need transmit the rand. Since we have the password/key, we just go through the first decryption algorithm and then use that result and try each of the 100 remaining possible ciphers. On average, it will take 50 tries to get it. No biggie - computers are fast at this. A good marketing guy will spin doctor this and have people thinking the extra time is just making their data more secure. This is much better then trying to transmit the encrypted rand (at least of the possibilities that I considered).

You lost me there - you have to have the key. Otherwise, when you try to decypher you will run through the 100 possible decyphers - but you will not know which one was the right one.

<snip>

Now, I didn't scamble the cypherbets 'cuz of time - but if I had, how would you know you broke the first cipher and could move on to the second?

It isn't hard. Assume that we had 10 ciphers and we randomly encoded a message with one of them and then randomly encoded that message with one of them again. Here's the pseudo-code to solve it using OOP.

Code:
Let cipher be an array of 10 ciphers
Let check be an alogirthm to check if a string is written in english
check returns a confidence value
Let cf be the minimum confidence value of a message that we want to see
Let msg be the encrypted message
Let tmp be a temporary string
Let plain be our attempt at the solution
Let key be the key (ie. the password)

for each element in cipher
tmp = cipher(msg,key)
for each element in cipher
plain = cipher(tmp,key)
if ( check(plain) >= cf )
display(plain)
give the user the option to stop the search or continue

A simple 'check' is pretty easy to implement. All you need is an array of the most common words in a language and then search each of the 100 decrypted messages for the one that had the most words - one of them is going to have significantly more matches than the others (in my experience, one of them will have more matches then all fo the others combined on any text longer then a 40 words). This part is similiar to how a computer attempts to break a cipher - after all, you're not going to want to sit around checking 2^1,000,000,000,000,000,000 screens of text looking for a weakness in 3DES, right?

Also, many, if not most (esp. during war), of the messages professional crytpoanalysts are trying to break are not in their native language. One advantedge of computer based attacks is that you don't need to know the foreign language to decipher the message.

This would actually be a good programming exercise for you to do. Let's keep it simple and use a Caesar shift cipher. Examples....

Code:
plaintext:  larry likes java
cipertext:  mbssz mjlft kbwb
(shift value =  1)

plaintext:  larry likes java
cipertext:  kzqqx khjdr izuz
(shift value = 25)

A program to derive the plaintext message from the cipher text shouldn't need to be more than 10 or 15 loc.

Manta wrote:
True enough - if you use the same shift (or even a different one) everytime, you are doing nothing. But look above - this isn't like that. I dropped 4 letters into 12 numbers back to 6 characters. Had I used transposition - and a different one for both - things get complicated. You could even have a method designed for frequency breaks by adding false characrters at a (seemingly) random interval.

Yeah, but what you're describing now reminds me more of an algorithm for a complicated classic cipher than a super cipher composed of several simple classic ciphers. You're also getting close to leaving the world of classic ciphers and entering the world of modern electronic ciphers. Do you know why?

Top

 Post subject: Posted: Sat Jul 03, 2004 2:03 pm
 Bitchin' Fast 3D Z8000*

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
MantaBase wrote:
Take the words that were solved for (falsely) out of Colby's post and run the program again.

Manta

No matter what words I remove - it just can't break that message. I've taken out the ones most likely to confuse the program.... key, public, private, etc. It is just completely befuddled by that paragraph.

I suspect the program is using a greedy algorithm (or has very limited backtracking capability) and cannot recover after heading down a bad path. Also, the language used to describe public/private key encryption is sufficiently different than normal english to confuse the attack. In the past, this automated attack has come close to solving many cryptograms for me - it normally gets close and I have to go back and correct one or two mistakes and finish off a few letters.

Top

 Post subject: Posted: Sun Jul 04, 2004 8:09 am
 I'd rather be modding!

Joined: Fri Jun 25, 2004 3:47 pm
Posts: 3731
Location: Las Vegas

It isn't hard. Assume that we had 10 ciphers and we randomly encoded a message with one of them and then randomly encoded that message with one of them again. Here's the pseudo-code to solve it using OOP.

Code:
Let cipher be an array of 10 ciphers
Let check be an alogirthm to check if a string is written in english
check returns a confidence value
Let cf be the minimum confidence value of a message that we want to see
Let msg be the encrypted message
Let tmp be a temporary string
Let plain be our attempt at the solution
Let key be the key (ie. the password)

for each element in cipher
tmp = cipher(msg,key)
for each element in cipher
plain = cipher(tmp,key)
if ( check(plain) >= cf )
display(plain)
give the user the option to stop the search or continue

A simple 'check' is pretty easy to implement. All you need is an array of the most common words in a language and then search each of the 100 decrypted messages for the one that had the most words - one of them is going to have significantly more matches than the others (in my experience, one of them will have more matches then all fo the others combined on any text longer then a 40 words). This part is similiar to how a computer attempts to break a cipher - after all, you're not going to want to sit around checking 2^1,000,000,000,000,000,000 screens of text looking for a weakness in 3DES, right?

Also, many, if not most (esp. during war), of the messages professional crytpoanalysts are trying to break are not in their native language. One advantedge of computer based attacks is that you don't need to know the foreign language to decipher the message.

This would actually be a good programming exercise for you to do. Let's keep it simple and use a Caesar shift cipher. Examples....

Code:
plaintext:  larry likes java
cipertext:  mbssz mjlft kbwb
(shift value =  1)

plaintext:  larry likes java
cipertext:  kzqqx khjdr izuz
(shift value = 25)

A program to derive the plaintext message from the cipher text shouldn't need to be more than 10 or 15 loc.

Manta wrote:
True enough - if you use the same shift (or even a different one) everytime, you are doing nothing. But look above - this isn't like that. I dropped 4 letters into 12 numbers back to 6 characters. Had I used transposition - and a different one for both - things get complicated. You could even have a method designed for frequency breaks by adding false characrters at a (seemingly) random interval.

Yeah, but what you're describing now reminds me more of an algorithm for a complicated classic cipher than a super cipher composed of several simple classic ciphers. You're also getting close to leaving the world of classic ciphers and entering the world of modern electronic ciphers. Do you know why?

I suspect because I am suggesting breaking the actual letters down into multiple components.

By "Supercipher" I meant "method". Like dropping to ascii triplets. Then the sub-ciphers I meant a fixed transposing technique (or other similar)

Like it hit the array at "28" - (the random pick)

2=drop to ascii method will be used
8=reverse the ascii table (or what ever)

Any single method is weak - but combined they are stonger because you would have to decypher more than one to get the proper words to resolve. Especially when you cipher tripets and treat ever two numbers as a character instead of three - in effect you are breaking the language.

Anyways - it would be interesting for me to go ahead and encipher it and then so if you can crack it and how hard it was. It will take time for me to code seriously (thought wise).

Manta

Manta

Top

 Post subject: Posted: Sun Jul 04, 2004 1:58 pm
 Bitchin' Fast 3D Z8000*

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
MantaBase wrote:
I suspect because I am suggesting breaking the actual letters down into multiple components.

Exactly. Although this isn't the definition of a modern cipher, it is one of the things that seperate them from classic ciphers. Classic ciphers tend to use the letter as the smallest unit for transposition and substitution. Modern ciphers are able to transpose and substitute at a lower level - it's all ones and zeros now.

Top

 Post subject: Posted: Sun Jul 04, 2004 2:21 pm
 I'd rather be modding!

Joined: Fri Jun 25, 2004 3:47 pm
Posts: 3731
Location: Las Vegas

Thats what I thought. So what is it when you do substitution? Like replacing the word "the" with "\$"?

Manta

Top

 Post subject: Posted: Mon Jul 05, 2004 1:48 am
 Bitchin' Fast 3D Z8000*

Joined: Tue Jun 29, 2004 11:32 pm
Posts: 2555
Location: Somewhere between compilation and linking
MantaBase wrote:

Thats what I thought. So what is it when you do substitution? Like replacing the word "the" with "\$"?

Manta

That is one example of substitiution. Replacing a letter, word, anything with another symbol is substitution. With digital ciphers, you can also subustitute within letters by subing 1's for 0'l or 0's for 1's. Some of the classic ciphers do interesting things to help improve their strength. They'll add null characters or use homophones - two or more symbols reprsenting the same character. The Vigenere is probably the strongest pure classic substitution cipher. That site has some really good explainations and tools.

Top

 Post subject: Posted: Wed Jul 07, 2004 11:34 am
 8086

Joined: Sun Jun 27, 2004 7:33 pm
Posts: 20
I've understood the basics of what guys have said. I also understand caeser shifts and such. My main breach in understanding comes from the mathematical functions... what such agorithm can be very easy to do one way but very difficult to undo? For example:

X % 5 = 2;
.: X = {2, 7, 12, ..., 2+5n}

Are you saying that for one letter in this ciphertext one could represent a letter by all the numbers in the set known as X? This would by my only feasible explanation, as then the private key would know that the function which represented that letter was X % 5 = 2, and it would be very difficult for an outside source to figure out that all the numbers in the set X all represent the same letter. Did I hit the nail on the head or do I have false hope?

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 2 of 2 [ 29 posts ] Go to page Previous  1, 2

 All times are UTC - 8 hours

#### Who is online

Users browsing this forum: No registered users and 4 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Maximum FAQs    Forum Rules, Posting Guidelines & Announcements    The Good, The Bad & The Banned    FAQs Help/Do It Yourself    PC Building Lab    The Help Desk    PC Modding    Education & Certification Hardware    Nuts & Bolts    Portable Talk    Appraisals, Deals & Bargains (oh my!) OS/Software/Programming    Windows Parlor    Alt.OS.Abode    Games Arena    Programmers' Paradise Networking/Internet    Internet Truckstop    Network Nook In/Out    Magazine and Book Feedback    Forum & Website Feedback    Dog Pound Team Maximum PC Folding at Home    Team Maximum PC - Folding at Home - FIND CURES TO DISEASES    Team MPC - Folding Gauntlets
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group