6
\$\begingroup\$

When I was about 13 or 14 years old, I was a little interested in cryptography (which is, after all, an interesting field). I learnt quite a lot since that time (it has been about 8 years since then), but I'm still very far away from considering myself an expert in cryptography.

Whatever, when I was at that age, I wrote this little Perl script which I just found on an old HD. (Saved as MyEncrypt.pm)

package MyEncrypt;

use strict;
use warnings;

my @_ALPHABET = ('a' .. 'z', 'A' .. 'Z', 0 .. 10, ' ');
my $_i = 0;
my %_ALPHABET = map { $_i++; $_ => $_i } @_ALPHABET;
$_i = 0;
my %_ALPHABET_REVERSE = map { $_i++; $_i => $_ } @_ALPHABET;

sub new {
    bless +{}, shift
}

sub set_password {
    my $self = shift;
    my $password = shift;
    $self->{hashed_password} = _hash_password($password);
    return $self;
}

sub encrypt {
    my $self = shift;
    my $input = shift;

    my $hashed_password = $self->{hashed_password};
    die "No password set.\n" unless $hashed_password;

    my @split = split(//, $input);

    my $output = shift;
    for (0 .. $#split) {
        my $new_number .= ($_ALPHABET{$split[$_]} + ($hashed_password ** ($_ + 1))) % $#_ALPHABET;
        $output .= $_ALPHABET_REVERSE{$new_number};
    }
    return $output;
}

sub _hash_password {
    my $password = shift;
    my $hash = 1;
    my $i = 1;
    for (split(//, $password)) {
        my $power = length($password) / (2 ** $i);
        $power = 1 if $power < 1;
        $hash *= int($_ALPHABET{$_} ** $power);
        $i++;
    }

    if(is_multiple_of_two($hash)) {
        $hash += 1;
    }

    while (length($hash) != 10) {
        no warnings;
        $hash *= $hash | join('', map { $_ALPHABET{$_} } split(//, $password));
        $hash =~ s/\.//g;
        $hash = substr($hash, 0, 10);
    }
    return $hash;
}

sub is_multiple_of_two {
    my $n = shift;
    my $log = log($n) / log(2);
    if($log == int($log)) {
        return 1;
    } else {
        return 0;
    }
}

1;

(It probably has the worst hashing-algorithm ever. I know).

This is my "test-program" for it:

use strict;
use warnings;
use MyEncrypt;

my $enc = MyEncrypt->new();
$enc->set_password('abc');
die $enc->encrypt("hello world");

My idea was this: We give it a password and it somehow generates a "hash" of it (here in a way that, I admit, I don't quite understand anymore. For some reason, it should be 10 digits long and these are generated by, until the password is 10 digits long, multiplying the password with the OR'd characters of the alphabet (where a = 1, ... A = 27, ...) and then cutting it to 10 characters or less, until this leads to a "hash"), which is then later used for this letter-by-letter-substitution:

x = (number of the actual letter + password_hash to the power of (position of this character + 1)) modulo the size of the alphabet

and then x is used to look for the letter numbered x, which will be added to the output-string. When gone through all the text, the output will have a completely different form of what it had as input. And when one letter changes in the password, the whole string is different.

E.g.:

string: "hello world", pass: "abc" => 9bkpXY1H0oR
string: "hello world", pass: "abcd" => HS4gVkuWX4U
string: "hello world", pass: "abcda" => DhAqIeHn9cr

and so on.

Of course, the code is terrible, the hashing-algorithm is probably the worst one ever and the idea is not really new, but I came up with it myself and at that time I was quite proud of myself for this. But how secure would this have been? How much time would one need to decrypt this and how would this be done? As I've said, I developed in many fields, but for some reason after that script I did not care so much about cryptography anymore and my knowledge there is quite limited.

\$\endgroup\$
  • 1
    \$\begingroup\$ I wonder whether this would belong on Information Security instead... \$\endgroup\$ – Schism Jul 24 '14 at 21:05
  • \$\begingroup\$ Are you seeking an actual review on this, or just the request in the title? \$\endgroup\$ – Jamal Jul 24 '14 at 21:08
  • 1
    \$\begingroup\$ Well, yes. Sorry then. I thought this here would be the correct place, but IS seems more appropriate. Thanks. \$\endgroup\$ – kono Jul 24 '14 at 21:13
  • \$\begingroup\$ I'm talking with other mods to determine where this best belongs. Please give me a moment. \$\endgroup\$ – Jamal Jul 24 '14 at 21:17
  • 4
    \$\begingroup\$ The advice on Information Security would be merely “don't roll your own crypto, we don't care why your scheme is broken, we just know it is”. Cryptography would be appropriate for specific questions, but “break my scheme” is explicitly banned: you're supposed to do some of the legwork on your own. You may want to research classical (pre-computer) crypto schemes and how they've been broken. You could also ask for help if you try some attack techniques like frequency analysis, but do some research first, as Cryptography is primarily about “serious” crypto. \$\endgroup\$ – Gilles Jul 24 '14 at 21:20
9
\$\begingroup\$

Your encryption scheme basically takes a string and does a one-to-one mapping of characters to 63 numbers (0 to 62). Ignoring this straightforward mapping of characters, your scheme basically is the i-th character of the ciphertext (1-indexed) is c[i] = (p[i] + H**i) % N, where N is the size of the alphabet (63), p[i] is i-th character of the plaintext, and H is the hash calculated from the password.

Decryption should be straightforward as p[i] = (c[i] - H**i) % N.

But the code doesn't work -- decryption is impossible

First, the code is seriously flawed as perl handles integer overflow by switching to floating point numbers rather than moving to a big integer library.

For example, for pw="abc" the hash is 8486571168 (as seen by inserting a print statement). Note for say the second character in the array you calculate 8486571168**2 in perl is 7.20218901895289e+19 -- an double precision floating point number. Note adding any number 0 to 63 to 7.20218901895289e+19 leaves the value unchanged in a double -- hence your code doesn't work -- it loses the original value of the plaintext due to rounding errors from using floating point math.

You can easily demonstrate this by using the same password (abc) to encrypt say "hBROKEN1234" or "hNOTWORKING" (or anything else starting with an h of this length). Regardless of the plaintext, the generated "ciphertext" will always be "9bkpXY1H0oR". You could fix this by using modular exponentiation library or a big-integer math library, or switching to a language like python that has big integer math built-in. Note, it suffices to show that an encryption method is broken if the same key encrypts two different plaintexts to the exact same ciphertext. If that happens clearly there is no decryption function, as the decryption function takes the key and the ciphertext and needs to recover the original plaintext.

Furthermore the algorithm is trivially attackable

Second, this scheme if fixed would be trivial to attack. You merely have to try to decrypt with all N (length of your alphabet) different values of the hash (modulo the alphabet size) and at least one of them should work.

If you understand modular arithmetic (if not see below) you will see your encryption method for each character c[i] = (p[i] + H**i) % N is exactly equivalent to c[i] = p[i] + (H % N)**i) % N. This is bad as there are only N possible values of H % N (and in our case N=63), so its trivial to try decrypting with H=0 to H=62 until you find something that is meaningful data.

Background on modular arithmetic

To see this note we are doing modular arithmetic. In modular arithmetic, there's the concept of congruent numbers; e.g., on a clock face (modulo 12) there's no difference between 3 o'clock or 15 o'clock, or 51 o'clock (48+3), so we say \$3 \equiv 15 \equiv 51 \;(\bmod 12)\$ -- the notation is to only write \$(\bmod N)\$ in parenthesis at the end, even though it applies to the whole equation (all sides).

When you do modular arithmetic for the most part, it doesn't matter if you take the modulus step early. This is easy to see for addition. if you add 7 hours to 3 o'clock, you get 10. Similarly if you add 31 hours (\$31 = 7 \bmod 12\$) to 15 o'clock, you again get 10 on the clock face. To formalize this notation, let's define two pairs of congruent numbers modulo N, specifically \$a \equiv A\;(\bmod N)\$ which means \$A = a + m N\$ for some integer \$m\$ (\$m\$ could be positive, negative or zero), and similarly let \$b \equiv B \;(\bmod N)\$ and \$B = b + n N\$ for some integer \$n\$. Doing the addition we get \$A + B = a + b + (m + n) N\$, and since \$m + n\$ is also an integer we just showed the \$A + B \equiv a + b\; (\bmod N)\$. You can do similar proofs for subtraction, multiplication, and exponentiation. works. The proof for multiplication: $$\begin{eqnarray} A B &=& (a + m N)(b + n N)\\ &=& a b + m b N + n a N + m n N N \\ &=& a b + (m b + n a + m n N) N \\ \therefore A B &\equiv& a b\; (\bmod N) \end{eqnarray}$$

Similarly for the base in exponentiation, we can show we can take the modulus (of the base) can be done early as

$$\begin{eqnarray} A^k &=& (a + m N)^k\\ &=& \sum_{i=0}^k {k \choose i}a^{k-i} (m N)^i \\ &=& a^k + \sum_{i=1}^k {k \choose i}a^{k-i} m^i N^i \\ &=& a^k + N \left(\sum_{i=1}^k {k \choose i}a^{k-i} m^i N^{i-1} \right) \\ \therefore A^k &\equiv& a^k\; (\bmod N) \end{eqnarray}$$

where the binomial theorem was used. Thus we are allowed to take an expression like (a + b**x) % N and change it to (a + (b % N)**x) % N and it won't change the result and thus only need to try all the values of (h % N) when brute-force decrypting.

\$\endgroup\$
  • 2
    \$\begingroup\$ Very nice and comprehensive answer, +1 ;) Welcome to Code Review! Feel free to drop by in Code Review Chat or on Code Review Meta \$\endgroup\$ – Vogel612 Jul 25 '14 at 10:32
  • 1
    \$\begingroup\$ @Edward - thanks for adding the mathjax formatting. I actually answered over in sec.se before the question over there was closed and it was suggested I move my answer here. At sec.se MathJax isn't loaded, so I have to resort to annoying unicode math operators and HTML sub/superscripts. \$\endgroup\$ – dr jimbob Jul 25 '14 at 15:07
2
\$\begingroup\$

Just some quick thoughts (I can't even read Perl nor do I know much about crypto).

  1. The last module could lead to problems in decrypting. I understand that you want your cypter text be easily viewable but what if your $new_number before the module happend to be bigger len(alphabet)? How would the decryptor know which of the infinte multiplies it was
  2. Why don't you want odd hashes? Just adding one makes hash-collision twice as likely
  3. Assuming that you have a static key and the attacker can force the encryption of text of his choosing - what happens if AAAAAAAAAAAAAAA is encrypted? As each letter is the same finding out the hash of the key can be done by analyzing the cypertext

And did you even write a decryption function to test whether your ecryption is any useful?

\$\endgroup\$
  • \$\begingroup\$ 1: Well, one of the things missing in that file is a decrypt-sub. I am "50/50 sure" that I had one (but in a later version of this file). But I might confuse this with some other attempts I made later, so there might not be one. Sadly, I only got this file here. 2: I remember having a problem with 2^n-like-numbers. Therefore, when the number could be written as 2^n, I just added one so that this does not cause problems. 3: I'm not sure whether I understand you correctly or not, but I just tried password: "a" and string: "AAAAAAAAAAAAAAA" and I got AhwhoXwKwNleork. \$\endgroup\$ – kono Jul 24 '14 at 21:44

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.