Register to reply

How long to crack this encryption by brute-force ?

Share this thread:
B0b-A
#1
Mar2-14, 12:41 PM
P: 50
How long to crack this encryption method by brute-force ?

I have a 64 character password created using a simple substitution cypher of the base 64 character set,
i.e. all characters are included in the password , none are repeated.

How long would it take a modern computer to crack this encryption method by brute force ?
i.e. to try all 64! permutations.
Phys.Org News Partner Science news on Phys.org
Experts defend operational earthquake forecasting, counter critiques
EU urged to convert TV frequencies to mobile broadband
Sierra Nevada freshwater runoff could drop 26 percent by 2100
phyzguy
#2
Mar2-14, 12:45 PM
P: 2,179
Well, since 64! = 10^89, it wouldn't even have gotten started before the sun goes red giant and incinerates the Earth.
B0b-A
#3
Mar2-14, 12:59 PM
P: 50
Quote Quote by phyzguy View Post
Well, since 64! = 10^89, it wouldn't even have gotten started before the sun goes red giant and incinerates the Earth.
Excellent news

Bill Simpson
#4
Mar3-14, 09:25 PM
P: 1,037
How long to crack this encryption by brute-force ?

Before you celebrate too much, think, is there ANY way that an adversary might guess a small subset of the 64 characters, have any way to quickly confirm that these cannot be correct, discard them and try the next small subset?

Since you haven't described anything about what you are using this password with I don't think there is any way for any one to tell whether there is a faster attack than just generating all 64! passwords.
berkeman
#5
Mar3-14, 10:23 PM
Mentor
berkeman's Avatar
P: 41,128
Thread closed for Mentor review...
berkeman
#6
Mar4-14, 11:04 AM
Mentor
berkeman's Avatar
P: 41,128
Thread re-opened.
Filip Larsen
#7
Mar4-14, 03:58 PM
PF Gold
Filip Larsen's Avatar
P: 961
Usually a password system have to be designed with care to avoid weaknesses, that is, attacks that on average will do far better than brute-force searching for the correct combination of characters.

For instance, a naive rejection of wrong passwords based on comparing bytes can leak information and open the system for timing attacks, low entropy during password generation can make the password much easier to guess (as Bill mentions), and if the passwords are sent to the system in the clear an attacker can simply eavesdrop on the communication to get one. And it is unfortunately also all to easy to introduce errors during design or coding that no one will ever notice until its too late, like forgetting to actually check the password, do it wrong (Apples recent SSL bug in Safari comes to mind), duplicating same password to different users, allowing session hijacking, and so on, all depending on the specific context of the system and how its implemented of course.

Remember, it doesn't matter if your front door is a 2 inch thick steel door with 5 independent locks if the window next to it is a plain old glass window. Obligatory xkcd: http://xkcd.com/538/

And, by the way, why use a combination of 64 distinct characters? It takes up space as a 384-bit string, but it only has around 296 bits of entropy. If you instead used a secure random 296-bit string you would get same brute-force strength using only 77% of the space.
Bill Simpson
#8
Mar5-14, 02:47 PM
P: 1,037
Quote Quote by Filip Larsen View Post
If you instead used a secure random 296-bit string you would get same brute-force strength using only 77% of the space.
When did 88 bits start making ANY difference in (almost) anything?

Would the code needed to put those 296 bits in storage be less than 88 bits larger than the code to put 64 characters in storage?

It is showing my age, but I just bought a thumb drive for $12 that had 8 MILLION TIMES more storage than the first computer they let us start programming on.
Filip Larsen
#9
Mar5-14, 04:32 PM
PF Gold
Filip Larsen's Avatar
P: 961
Quote Quote by Bill Simpson View Post
When did 88 bits start making ANY difference in (almost) anything?
I probably didn't explain that well enough. As a rule of thumb in cryptography it is generally not a good idea to carry around a lot of redundancy (here 88 out of 384 bits) unless its serves some specific purpose.

For instance, passwords that are to be created, read, remembered, and typed in by humans, have a high amount of wasted or redundant bits when stored or transported as character strings (one should probably not expect an average entropy above a few bits per character in normal user passwords), but this is acceptable as it is used to make password amendable to human mental processes.

However, in this thread the OP mentions a password (or key) created as a permutation of a 64 symbol set, which, in the case humans have to handle it, could be base-64 encoded as a 48 characters string. Since I think it is fair to assume that no human can be expected be able to use the extra 88 bits of redundancy in those 48 characters the key may as well be expressed as a 37 character base-64 encoded key without redundancy.

Also, if we assume the permutation has to be generated by an algorithm (on a computer), then this algorithm would need at least 296 bits of entropy anyway to generate a secure (i.e. unbiased) 384-bit "permutated" key, so its not like such key could be made with less effort or less entropy. Without specific purpose the extra 88 bits truly are wasted bits.
Baluncore
#10
Mar6-14, 06:44 AM
Sci Advisor
Thanks
P: 1,924
Filip Larsen is correct.

Quote Quote by B0b-A
Excellent news
Knowing the key makes it possible for a cipher clerk to reliably decode the message. But a cryptanalyst can quickly solve a substitution cipher, without any need to know the password or key. With substitution ciphers, the enemy cryptanalysts often read the clear text before the intended recipient.

An amateur fixates only on the most complex part of their invented system, while a skilled cryptanalyst is aware of all the potential weaknesses in the system. The cryptanalyst avoids the complexities and would almost never be attracted to use brute force, since that option will always be designed to waste their time.

A very common problem with amateur cipher systems is that too much emphasis is placed on one part of the system. The resultant neglect means other weaknesses remain wide open.

If you put three locks on the front door, two on the back, and one on each window, the burglar will get in through the roof cavity. If you focus on strengthening your normal method of access, you will only make things more difficult for yourself.
B0b-A
#11
Mar6-14, 09:29 AM
P: 50
My first post was a simplification, here's a better description of what I'm actually doing ...

My plaintext is converted into base64 by a program freely available on the internet.

I modified this program by shuffling the string in the program used to create base64 output, namely

"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/"

to something like

"upH6yGYWIsFORmfv9e8rXZwKj1PaV/ziLNqM5xoACnBk0tcUdJ73gQ+SDTbE2hl4"

So what was an "A" in the base64 output is now substituted by "u" , "B" is now substituted by "p" , etc.

Maybe a "deranged alphabet" would be a better description of the encryption method I'm using.

The plaintext messages are never less than 64 characters long , ( usually several hundred characters ).

So even if someone has a copy of the free program which converts plaintext to base64 , and vice-versa ,
it won't decipher my encrypted text because their copy doesn't have my shuffled alphabet.
They'd have to try all permutations of 64 characters (all 64!) to crack the code , [ I think (?_?) ]

[ BTW frequency analysis won't help anyone trying to crack this code:
binary-shenanigans during the conversion from English to base64 to avoid that weakness ]
Filip Larsen
#12
Mar6-14, 10:45 AM
PF Gold
Filip Larsen's Avatar
P: 961
Quote Quote by B0b-A View Post
So even if someone has a copy of the free program which converts plaintext to base64 , and vice-versa ,
it won't decipher my encrypted text because their copy doesn't have my shuffled alphabet.
They'd have to try all permutations of 64 characters (all 64!) to crack the code , [ I think (?_?) ]

[ BTW frequency analysis won't help anyone trying to crack this code:
binary-shenanigans during the conversion from English to base64 to avoid that weakness ]
Ok, all my comments were made with the assumption that this was for a password. Using it for encryption changes all.

Your scheme is a simple substitution cipher(*) and and you can expect a competent adversary to more or less break it after one or two ciphertext messages. And base-64 encoding will not makes it less susceptible to frequency analysis because an adversary can just do a standard base-64 decoding of your ciphertext and continue a character (i.e. 8-bit character) based frequency analysis on that. Since base-64 encodes 3 bytes blocks to 4 character blocks he could also, with on average around 33% additional use of ciphertext, do frequency analysis on the ciphertext directly. In short, your scheme is trivially broken.

(*) It is not clear to me if your program really base-64 encode your plaintext (but with a different alphabet) or if you only substitute characters. I assume you do the former and not the later.
Baluncore
#13
Mar6-14, 11:17 AM
Sci Advisor
Thanks
P: 1,924
B0b-A
If only cryptanalysis was that difficult. Ciphers of that complexity were being routinely broken during WW1, 100 years ago, using a pencil and paper. It is really good to know that “the plaintext messages are never less than 64 characters long , ( usually several hundred characters )”. The longer the message the easier it is to break. You are living in a paradise of false security.

Every time you add a complication to a cipher, you make it more difficult for yourself in two ways. Firstly; you are less able to analyse the remaining weaknesses, and secondly; because every time you pass a message you must overcome that complexity twice.

The prerequisite for cipher design is cracking other's cipher systems, doing cryptic crosswords, and studying number theory at a third year university level. If you have not read “The Codebreakers” by David Kahn, then you should get yourself a copy.
nsaspook
#14
Mar6-14, 11:22 AM
P: 649
Quote Quote by B0b-A View Post
My first post was a simplification, here's a better description of what I'm actually doing ...

...

[ BTW frequency analysis won't help anyone trying to crack this code:
binary-shenanigans during the conversion from English to base64 to avoid that weakness ]
Now it's not a Simple substitution cipher (like ROT-13) as you have at least an P-box/S-box to hide the clear text from the clear key substitution like in a trivial Transposition cipher. One key to decide if your system is secure (a channel for information and not a 'one time pad') to the see how much Chosen/Known plaintext is needed to effectively attack the system and reveal the key or if it can be broken with ciphertext methods only.

http://www.giac.org/cissp-papers/57.pdf
B0b-A
#15
Mar6-14, 11:36 AM
P: 50
Quote Quote by Filip Larsen View Post
(*) It is not clear to me if your program really base-64 encode your plaintext (but with a different alphabet) or if you only substitute characters. I assume you do the former and not the later.
The encoding of the plaintext into base64 is not done in a standard or consistent way : the "binary shenanigans" includes, ( but is not limited to ), a (pseudo)random initialization vector so the same plaintext appears as a different ciphertext each time it is encrypted.

So intercepting many cyphertexts won't help because of the different initialization vectors each plaintext is encoded differently into base64 : so encryption is not consistent between messages. Then my shuffled base64 alphabet is applied for good measure, [ probably overkill ].
nsaspook
#16
Mar6-14, 12:49 PM
P: 649
Quote Quote by B0b-A View Post
The encoding of the plaintext into base64 is not done in a standard or consistent way : the "binary shenanigans" includes, ( but is not limited to ), a (pseudo)random initialization vector so the same plaintext appears as a different ciphertext each time it is encrypted.
Now you have to be sure your method of using a (cryptographically secure) hashing function to generate the seed used by the (cryptographically secure) PRNG is cryptographically secure not just mathematically correct as you must assume the 'enemy' will somehow get a copy of your program/device to understand its structure. As been said before each complexity also creates an opportunity to crack your encryption.

http://en.wikipedia.org/wiki/Cryptog..._hash_function
http://en.wikipedia.org/wiki/Cryptog...mber_generator
http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf
Filip Larsen
#17
Mar6-14, 01:21 PM
PF Gold
Filip Larsen's Avatar
P: 961
Quote Quote by B0b-A View Post
The encoding of the plaintext into base64 is not done in a standard or consistent way : the "binary shenanigans" includes, ( but is not limited to ), a (pseudo)random initialization vector so the same plaintext appears as a different ciphertext each time it is encrypted.

So intercepting many cyphertexts won't help because of the different initialization vectors each plaintext is encoded differently into base64 : so encryption is not consistent between messages. Then my shuffled base64 alphabet is applied for good measure, [ probably overkill ].
Yes, from what you have described so far it does seems likely that your base-64 encoding with a special alphabet doesn't add any security at all to your scheme. The security then alone rests with your "binary operations" and if the algorithm (or even implementation) of those are home-made in any way you should expect that they too will be easy to break by an analyst.

Of course, if your expected adversary is not Eve from NSA, but merely postman Pat from down the road, then a simple substitution cipher may be good enough for you. That is, unless Pat has internet and knows how to google ...
Baluncore
#18
Mar6-14, 02:23 PM
Sci Advisor
Thanks
P: 1,924
B0b-A. Do you really have a need for a strong cipher?
What makes you think your data is worth reading?
It is often safer to use plain text, and to avoid criminal activity.

When you are framed on a drug trafficking charge, your unbroken encrypted messages will be presented as evidence of conspiracy and organised crime.

By employing a secure cipher system, you nail a target to your forehead.


Register to reply

Related Discussions
How long for a computer to write out a Googolplex (Not Homework) General Math 9
How long can I run my computer using an Inverter? Electrical Engineering 8
Computer could retain any information as long as its user desires Electrical Engineering 1
How long can we wait before we absolutely must take steps to protectagainst quantum computer attacks? General Physics 0
How long can you look a computer screen? General Discussion 17