Bit key length, encryption and brute-force attacks

This thread probably fits here :slight_smile:

I’m trying to get my head around the whole encryption thing, but for starters:

Ok. Let’s say i have a 32bit key. This means the following

[00000000000000000000000000000000] → this is one container (combination) of 32 bits (0/1).
.
.

2,1 billion and something of such combinations
.
.
.
[11111111111111111111111111111111] → the final one

My key would therefore have 2,1 billion containers of different combinations. A computer would thus have to go trough all the billion combinations in different arrangements while searching for the key. Right?

So let’s say my key is just ABC

[01011000000000000000000000000000] → let’s say this is the encoding for A
[11000101000000000000000000000000] → B
[01100001000000000000000000000000] → C
[00000000000000000000000000000000] → 0
[00000000000000000000000000000000] → 0
[00000000000000000000000000000000] → 0
.
.
.
.
[00000000000000000000000000000000] → 0

So if the computer decided to just randomly check each combination…the would need to go trough all of them despite most of them being just 0? Do codebreaking computers have algorithms to first check if the password contains human usable symbols? Ant then just random combinations?

Am i even getting at this correctly?

tnx

For a password entered by a human a sensible approach would be to try first words from dictionary, combinations of such words like dog-cat then letters and numbers and other ASCII characters.

There is an easy way of calculating the entropy (ie. the randomness) of a given human-readable key. (This assumes that the key is chosen at random).

Use a scientific calculator, and work out the entropy per character, and multiply by the number of characters.

For example, if you choose a passphrase or key made of lowercase alphabetic characters (a-z) then there are 26 possible combinations.

Use the calculator to work out;

log (combinations) / log (2)

You can use log to the base 10, or natural logs, you will get the same answer.

eg.

log (26) / log (2) = 4.7004

Now multiply by the length of the word you are planning to use. For example, "swordfish" = 9 characters.

entropy = 4.7004 * 9 = 42.30 bits

Thus, using "swordfish" as a password gives you only 42 bits of key, which could probably be broken in under a second.

The other problem with real words, like "swordfish", is that they can be subjected to a dictionary attack. Say you choose any word from a possible 100,000 words that you know.

entropy = log (100000) / log (2) = 16.61

So in fact, "swordfish" is an appallingly bad choice of password. It is equivalent to using a 17-bit key.

Of course, things improve if you use more than one word, but to get a full 256 bits of entropy from using words from a 100,000-word dictionary you need over 15 words!

words needed = 256 / 16.61 = 15.41

Using 256 bits of entropy is probably overkill today, probably around 100 is enough for domestic purposes.

Aha.

So. Basically a 9 character word if brute forced with random attempts would be tougher to guess than a whole word out of 100k elements (in case of dictionary attacks).

With the 9 character word you'd have to go trough 2.1*10^12 attempts. With a dictionary attack just 100k attempts.
Three words from a dictionary would yield about the same entropy as the 9 random character word. Interesting.

I'd like to ask, probably a very silly question, but to understand things correctly:

If we, let's say, make a password just one element in length, and this element is a character from our alphabet (a pool 26 characters). This of course means jut 4 bits of entropy or 26 attempts.

32bit of information would mean that you have a pool 2.1billion distinct "characters" or better said combinations or "potential characters".
If we also use a password jut one element in length, but use a "character" from a 32bit pool that would mean that we'd go trough the 2.1 billion attempts (hence 32 bits of entropy).
In human understandable terms this would mean that this one element in the password could potentially be a number between 0 and 2147483647 (2^31 -1). Right?

So, a 32bit key could look like this (to a human): "tkndcos" ( 4.7bits * 7 = 32.9 bits of entropy...if using just alphabet letters).
Or it could look like this (to a machine): [00010000001000010000000001100000] (32 bits of entropy)

What i'm probably trying to ask...how does a key actually look or how it is interpreted?

Let me phrase it a bit differently. Let's say i have an encryption system like AES, but using jus a 32bit key.

I encrypt a file with this key. Let's say the key is in binary format.
I use this key [10000000000000000000000000000000] (which i guess would be a representation of 1 in human terms).

Then i expose it to a brute force attack. The way i see it...the brute force could start executing in different ways. Either it could start with the first combination
[00000000000000000000000000000000]
and the move on to the next.
It could start from the back
[11111111111111111111111111111111]
The middle. Or it could start at random.
If this is the case i see several problems here. If my key is a combination that is either from the beginning part or the end...this means the attack could find out my key almost instantly or it might have to go trough all the two billion combinations.

To me this doesn't sound right. Probably because it isn't. But i can't get my head around it.

Yes, a brute force attack could guess correctly the first time. Crackers probably spend a lot of time sorting brute force dictionaries by likelyhood. So "Password123" is an early guess, and "CaseTTe" comes later...

Of course, it also helps that the keys used are almost always more than 32bits...

Encryption is indeed complicated. Note that password authentication is one small subset of encryption. If you send something like an encrypted email using "AES encryption", the "operation" of your password with any particular piece of the email will not yield the unencrypted piece of the email. Instead, the email is divided into smaller blocks of text, each of which is coded with a sub-key that is derived from the original key PLUS all the previous data in the email. And the password "as typed" by the user is hardly ever used "as-is" as a key that results in adversary-viewable text. Instead, it is "mixed" with other entropy (system key, timestamp, username, etc.) In ways that are "difficult" (which is mathematically defined!) to undo. So you type in a 20 character password, and that gets mixed with other data to give you a 128bit key, which is used to generate a sequence of additional 128bit keys that each operate on a 64byte block of your email.

I can recommend the Stanford Online Cryptography class: https://www.coursera.org/course/crypto (which starts soon.) However, it requires a relatively strong programming background. (OTOH, I learned a lot in the class without doing many of the programming assignments, so YMMV.) There were a couple of important take-aways:

  1. NEVER try to invent your own encryption algorithm.
  2. 2^32 (~4billion, BTW. Not 2B) guesses is NOTHING to a modern computer. It takes a few minutes.
  3. 2^128 is a much bigger number than 2^32. Even though it's only four times as many bits.
  4. LOTS of existing encryption schemes have bugs :frowning:
  5. There are subtleties. For example, if you have a good encryption algorithm, you would be unable to derive the key, or decode a 2nd encrypted message, even if you know the algorithm, and have a full encrypted AND unencrypted previous message. In fact, you should be unable to tell that the 2nd encrypted message is a duplicate of the 1st message (if it is.)

If you get bored try looking at "oclHashcat" which I believe is currently the most popular password cracking program. And to answer your question regarding the attacking from the start/middle/end it does perform its attacks from the alphabetic start (with the exception of using a "wordlist" which might not be alphabetically organized). So, yeah, passwords that start with "Z" are usually the strongest.

Handy program. I use it regularly to ensure my users are sticking with strong passwords.