How long to crack this encryption by brute-force ?

  1. 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.
    Last edited: Mar 2, 2014
  2. jcsd
  3. Well, since 64! = 10^89, it wouldn't even have gotten started before the sun goes red giant and incinerates the Earth.
  4. Excellent news :smile:
  5. 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.
  6. berkeman

    Staff: Mentor

    Thread closed for Mentor review...
  7. berkeman

    Staff: Mentor

    Thread re-opened.
  8. Filip Larsen

    Filip Larsen 1,016
    Gold Member

    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:

    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.
  9. 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.
  10. Filip Larsen

    Filip Larsen 1,016
    Gold Member

    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.
  11. Baluncore

    Baluncore 3,216
    Science Advisor

    Filip Larsen is correct.

    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.
  12. 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


    to something like


    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 ]
    Last edited: Mar 6, 2014
  13. Filip Larsen

    Filip Larsen 1,016
    Gold Member

    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.
  14. Baluncore

    Baluncore 3,216
    Science Advisor

    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.
  15. nsaspook

    nsaspook 1,307
    Science Advisor

    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.
    Last edited: Mar 6, 2014
  16. 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 ].
  17. nsaspook

    nsaspook 1,307
    Science Advisor

    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.
    Last edited: Mar 6, 2014
  18. Filip Larsen

    Filip Larsen 1,016
    Gold Member

    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 ...
  19. Baluncore

    Baluncore 3,216
    Science Advisor

    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.
  20. AlephZero

    AlephZero 7,244
    Science Advisor
    Homework Helper

    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!)
  21. Filip Larsen

    Filip Larsen 1,016
    Gold Member

    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.

Know someone interested in this topic? Share this thead via email, Google+, Twitter, or Facebook

Have something to add?

Draft saved Draft deleted
Similar discussions for: How long to crack this encryption by brute-force ?