Q:

Total password count, given length and pool size

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!

A:

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:

length equal to 8
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.

