How long to crack this encryption by brute-force ?

[B0b-A]

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.

 

[phyzguy]

Well, since 64! = 10^89, it wouldn't even have gotten started before the sun goes red giant and incinerates the Earth.

 

[B0b-A]

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]

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 anyone to tell whether there is a faster attack than just generating all 64! passwords.

 

[berkeman]

Thread closed for Mentor review...

 

[berkeman]

Thread re-opened.

 

[Filip Larsen]

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]

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]

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]

Filip Larsen is correct.

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]

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]

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]

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]

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]

(*) 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]

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/Cryptographic_hash_function
http://en.wikipedia.org/wiki/Cryptographically_secure_pseudorandom_number_generator
http://netlab.cs.ucla.edu/wiki/files/shannon1949.pdf

 

[Filip Larsen]

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]

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.

 

[AlephZero]

In short, your scheme is trivially broken.

I think the main difficulty that "Postman Pat" would have breaking this, is guessing what type of encryption system you used. If that fact is public knowledge, cracking the details is easy enough, as others have said.

Of course principle applies at any level of security. Cracking the WWII Enigma code became a lot easier, after the Allies captured a working Enigma machine.

(And the fact that some dumbo in the middle of the North African desert sent a daily status report with exactly the same message, "nothing to report", also helped!)

 

[Filip Larsen]

I think the main difficulty that "Postman Pat" would have breaking this, is guessing what type of encryption system you used. If that fact is public knowledge, cracking the details is easy enough, as others have said.

Security by obscurity [1] is generally considered a "fallacy" nowadays (as the DRM tech business repeatedly has found out the hard way). All Pat needs to do in this case is not to try break the encryption himself but merely enroll someone who can, and that is very easy and fairly cheap these day I'm told.

[1] http://en.wikipedia.org/wiki/Security_through_obscurity

 

[nsaspook]

I would suggest the OP and the 'Postman' take a look at CrypTool: http://www.cryptool.org/en/cryptool2-en

 

[AlephZero]

Security by obscurity [1] is generally considered a "fallacy" nowadays (as the DRM tech business repeatedly has found out the hard way). All Pat needs to do in this case is not to try break the encryption himself but merely enroll someone who can, and that is very easy and fairly cheap these day I'm told.

I don't disagree with that, but I was assuming the only help he would have was feline

 

[harborsparrow]

Well...if you're truly worried about cyber attacks, let me reassure you (not). Google recently widened all their keys to 2048 bits: http://news.cnet.com/8301-1023_3-57...es-2048-bit-security-upgrade-for-web-privacy/

As for brute force attacks, "how long" it takes depends on luck (i.e., it could find your private key on the 3rd try). If you are worried about best case, besides the maximum number of operations a brute force search might take, one has to know the computing platform. So if the tries are on a massively parallel platform, it could be relatively faster.

 

[harborsparrow]

Note, I changed the above after posting. I had gotten sidetracked and tried to make it back on topic. Sorry!

 

[B0b-A]

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.

I'm not engaged in any criminal activity : my main use for this encryption is storing passwords on removable media. If I lost a memory-stick with my passwords for online-logins in plaintext, anyone who found it could have access to online accounts 8¬o

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

That's a paranoid notion, but if required by law* I can decrypt the messages to show they are legitimate.
[ * I'm in the UK where you can go to jail if you don't tell Constable Plod the password ... http://www.theregister.co.uk/2007/10/03/ripa-decryption_keys_power/ ]

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

If one wanted to conceal an encrypted message one would employ steganography.

 

[B0b-A]

(And the fact that some dumbo in the middle of the North African desert sent a daily status report with exactly the same message, "nothing to report", also helped!)

That's where the initialization vector comes in handy : different every time ...

http://www.fourmilab.ch/javascrypt/

 

[Baluncore]

The local secure storage of your own passwords is a quite different scenario to passing regular traffic over an open channel.

We can assume that your opposition is a criminal who has access to your encrypted vault of passwords, to your encryption algorithm and to one of your clear passwords. They need the key to your encrypted vault.

The problem then reduces to one of reversing the system for each encrypted password.
For each encrypted password, they calculate the vault key that would be needed to generate the one known password. For n encrypted passwords in the vault, that produces n trial keys. Each of those n trial keys can then be tested against other encrypted passwords in the vault to identify which of the n is the valid key to your vault.

The partial trial keys may be sparse and there are complexities, but it certainly does not need a brute force search. The greatest weakness is probably the password table format in the vault coupled with the simple substitution.

 

[Baluncore]

Cryptography is hard. Most software developers realize this. Security dogma of "don't invent your own crypto; use standard algorithms" has been a "best practice" for some time. But what does this mean?

https://code.google.com/p/bletchley/