Gabriele Biondo

The problem of hiding stuff

Definitions

Cryptography is defined by Wikipedia as

Cryptography or cryptology (from Ancient Greek: κρυπτός, translit. kryptós “hidden, secret”; and γράφειν graphein, “to write”, or -λογία -logia, “study”, respectively) is the practice and study of techniques for secure communication in the presence of third parties called adversaries.

A very high level definition that can be shortened as “the science of hiding information as much/long as possible”. Before even discussing the key concepts, like “hiding” and “information”, let us focus to the boundaries: “as long as possible”.

“As long as possible”

Whoever has done some hacking in their lives, know that there is no thing such as “perfect security”, no state of perfect inviolability. Given enough time and enough resources, all systems (intended as the interaction between people, processes, products and technology managing information) can be violated: people may be bribed or blackmailed; processes always have brown corners that have never been tested, technology has 0-days, products always end up being an enlargement of attack surface.

So, the idea is protecting something – in this case, the confidentiality of a piece of information – as much as possible and for as long as possible.

Let us face the standard case:

Password breaking

This is a basic definition, we will use it consistently throughout all these notes:

Alphabeth: the set of acceptable symbols for a password. We shall indicate it as \(\mathcal{A}\). For the sake of simplicity, assume an alphabeth containing uppercase letters, lowercase letters, and the digits from 0 to 9. Formally, this would be indicated as

\(\mathcal{A}=\{0,1,\dots,9,a,b,\dots,z,A,B,\dots,Z\}\)

and consider that this set is comprised of 26+26+10=62 elements: \(\mid\mathcal{A}\mid=62\).

A Password is a sequence of \(k>0\) symbols of the alphabeth, that gets encrypted via a given algorithm. We will come back later on this one, for the very moment, let us think about it intuitively. Then, the password can be modeled as \(a_1a_2\dots a_k\) where \(a_i\in \mathcal{A}\) for \(i=1,2,\dots k\).

Now, \(a_1\) can be chosen in 62 different ways. Subsequently,  \(a_2\) can be chosen in 62 different ways; and so on, until  \(a_k\), which can be chosen in 62 ways. It is immediate that this gives raise to at least \(62\cdot62\cdot62\dots62\), and this product has \(k\) factors, giving raise to \(62^k\) different passwords of length \(k\).

The collection of all these passwords is the Solution tree, one can imagine it as depicted below:

so, at the first level, there are the \(62\) 1-characters passwords, at level 2 there are \(62^2\) 2-characters passwords take place, and so on, until level k, with \(62^k\) different passwords.

It is easy to see that bruteforcing a password implies testing:

  • all level one passwords
  • all level two passwords
  • all level \(k-1\) passwords

in average, half of level \(k\) passwords. The order of magnitude, anyway, is always all of level \(k\) passwords.

Shortly, the number of passwords to test is

\(S\left(k\right):=\sum_{l=1}^k 62^l=\frac{1-62^{k+1}}{1-62}-1\)

see here for proof. Now, it is evident that \(S\left(k\right)=\mathcal{O}\left(62^k\right) \), and hence:

  1. the bruteforce method has exponential complexity (in other words, the problem explodes with the number of characters comprising the password)
  2. however, the method converges (in other words, “sooner or later” a solution is found).

Chiefly, this does not mean that the problem cannot be solved – actually it can! – the point is that solving such a problem can literally take forever.

That’s the idea. Creating a problem in a relatively short time that can be solved in a quantity of time that exceeds the meaningful.

 

1 thought on “The problem of hiding stuff

Leave a Reply

Your email address will not be published. Required fields are marked *