1
$\begingroup$

First, if my password is exactly 8 characters long, derived from a pool of 95 characters, then is the total amount of passwords I can create simply $95^8$ (6,​634,​204,​312,​890,​625)?

Secondly, if my password can be upto 8 characters long, derived from a pool of 95 characters, then is the total amount of passwords I can create computed the same way, or would it be something like $95^0$ + $95^1$ + $95^2$ + $95^3$ + $95^4$ + $95^5$ + $95^6$ + $95^7$ + $95^8$ (6,704,780,954,517,120)?

Is the correct term for these called permutations, or search space or key space, or...?

Thanks for the assist!

$\endgroup$
  • $\begingroup$ Don't forget to add $95^0$ :p $\endgroup$ – SEJPM May 25 '17 at 14:48
  • $\begingroup$ What are you counting ? I suggest you think about that before adding that '1'... $\endgroup$ – Biv May 25 '17 at 14:58
  • $\begingroup$ What am I counting? The amount of 8-character passwords I can create from a pool of 95 characters, given the two mentioned scenarios. I don't really care if I'm off by '1'. $\endgroup$ – Mac May 25 '17 at 15:03
  • $\begingroup$ @Biv pls. The empty password is the best password :p $\endgroup$ – SEJPM May 25 '17 at 15:19
  • $\begingroup$ @Mac It's not about being off by one or whichever number, it's about getting it right. Combinatorics is one of those fields where you can easily screw up everything because you think it's straightforward. $\endgroup$ – Dreadlockyx May 25 '17 at 15:50
1
$\begingroup$

I believe you are getting confused by a few terms here. Let's get through what you mentioned.

Key space refers to all possible keys that may be used for an algorithm which handles keys at some point (input or output).

For instance, there exists a total of $2^{128}$ keys for AES-128 because in this case the encryption key is defined on 128 bits.

Search space is used when you look for something (eg. password) and you want to know the total number of possible values that match your search.

For instance, if you look for a password made out of (case-sensitive) alphanumerical characters and of length 10, any character in the password string can take one of the 62 possible values. Hence, the search space is $62^{10}$.

Permutations are specific ways of counting elements within the field of combinatorics. Just like combinations, they are used when one arranges items from some sample space. There is however a key difference between the two: order counts for permutations but not for combinations.

For instance, if you look for the number of ways to select up to two items without order from the set $(a,b,c)$, you will find $\sum_{i=1}^{2} \frac{3!}{i!(3-i)!}=6$. With order, you find $\sum_{i=1}^{2} \frac{3!}{(3-i)!}=9$. This is because the two elements $(a,b)$ and $(b,a)$ and alike are considered to be the same in the first case, but not in the second one.


Now, going back to your question, you want to know how to call your password lookups given a sample space of $n=95$ elements. The two cases are:

  1. length equal to 8
  2. length up to 8

In both cases, any position can take $n$ possible values because repetition is allowed (eg. using "A" twice is not forbidden).

With a fixed length of 8, the search space is thus $95^8 = 6'634'204'312'890'625$. This is a permutation with repetition because the strings "abc" and "bca" are counted as two distinct passwords (permutation) and that any element from the sample space may be used more than once (repetition, as stated above).

With a length up to 8, you need to count all possible passwords starting from the bottom. Hence, the search space is $\sum_{i=0}^{8} 95^{i} = 6'704'780'954'517'121$. The null or empty string is included ($95^0$) because no lower bound was given. The search type/name stays the same though.

$\endgroup$
1
$\begingroup$

Possible combinations (permutations) = sequenceOptions to the power of sequenceLength

Assuming a pool of 95 sequence options

  • sequenceLength 0 = 0 permutations (950)
  • sequenceLength 1 = 95 permutations (951)
  • sequenceLength 2 = 9025 permutations (952)
  • sequenceLength 3 = 857375 permutations (953)
  • etc

This is not limited to passwords/characters. For example, when a password is put through a key derivation algorithm, it ends up as a string of bits for which there are two options; 0 and 1. Hence, a 256 bit length key contains 2256 permutations.

More simply, a 4-digit numeric pincode has 10000 (104) possible permutations.

As for the second part of your question, yes; if the sequenceLength were <= 8 then the total number of permutations would be 950 + 951 + 952 + 953 + 954 + 955 + 956 + 957 + 958

Of course, the above assumes that each option in the sequence can appear more than once. If that's not the case then factorials come into play.

$\endgroup$
  • $\begingroup$ As stated in the comment section below OP's post, the null string has to be included. $\endgroup$ – Dreadlockyx May 25 '17 at 18:30
  • $\begingroup$ It's there - you just can't see it $\endgroup$ – hunter May 25 '17 at 19:27
  • $\begingroup$ Where you wrote "total number of permutations" there should be $95^0$ (not the case atm) $\endgroup$ – Dreadlockyx May 25 '17 at 19:38
  • 2
    $\begingroup$ hehe yes I was kidding. Thanks - It's corrected now $\endgroup$ – hunter May 25 '17 at 19:43
  • $\begingroup$ Good explanation, and thanks for mentioning factorials. $\endgroup$ – Mac May 26 '17 at 2:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.