1. Einleitung
Nachdem bereits die Caesar-Verschlüsselung in PHP vorgestellt wurde, soll in diesem Artikel das grundsätzliche Vorgehen ausgebaut werden, um so Verschlüsselungsalgorithmen zu erhalten, die tatsächlich ein Mindestmaß an Sicherheit bieten. Nachfolgend werden drei Verfahren vorgestellt, jeweils mit Funktion zum ver- und entschlüsseln von Strings. Diese Funktionen lauten, grob zusammengefasst (Erklärungen beziehen sich jeweils auf das Verschlüsseln):
- encodeRand/decodeRand: Durchläuft einen String, bildet von jedem Zeichen jeweils den ASCII-Dezimalwert und erhöht diesen um einen Zufallswert, der von einem übergebenen Schlüssel abhängig ist.
- encodeStrtr/decodeStrtr: Bildet anhand eines übergebenen Schlüssels ein Ausgangs- und ein Zielalphabet. Jedes Zeichen aus dem Ausgangsalphabet wird zum analogen Zeichen aus dem Zielalphabet geändert.
- addJunk/removeJunk: Fügt auf Basis eines übergebenen Schlüssels an zufälligen Stellen unnütze Zeichen („Müll”) ein.
Alle drei Verfahren basieren auf dem Zufallsgenerator von PHP. Diesem kann ein Integer als Schlüssel („seed”) übergeben werden. Ist dieser Schlüssel gleich, dann sind auch die produzierten Zufallszahlen gleich. So sind die Änderungen an den Strings scheinbar zufällig, gleichzeitig aber auch ausreichend deterministisch, sodass sie wieder umgekehrt werden können — vorausgesetzt der Schlüssel bzw. Seed ist bekannt.
2. encodeRand() / decodeRand()
Die Funktion encodeRand($str, $seed) nimmt einen String $str und einen Schlüssel $seed (Integer) entgegen. Sie „startet” den PHP-Zufallsgenerator mit dem Schlüssel, sodass alle berechneten Zufallszahlen vom Schlüssel abhängen. Anschließend iteriert sie über sämtliche Bytes des Strings und berechnet jeweils den zugehörigen ASCII-Wert. Dieser ASCII-Wert wird mit einer Prinzahl (hier: 3) multipliziert und mit der nächsten Zufallszahl im Bereich zwischen 350 und 16000 addiert. So hat der sich ergebende neue Wert für das Byte praktisch keinen Bezug mehr zum alten Wert. Insbesondere wird auf diese Weise jedem Zeichen im String ein (in der Regel) anderer Wert zugeordnet. Einfache Attacken der Art „das am häufigsten vorkommende Zeichen ist vermutlich ein e” sind dadurch nicht mehr möglich.
Die Funktion decodeRand() muss analog nur die berechneten Zahlen auslesen und über diese iterieren. Bei jeder Iteration wird zuerst der nächste Zufallswert zwischen 350 und 16000 abgezogen und durch 3 geteilt. Die berechnete Zahl wird per chr() wieder in das passende Zeichen umgewandelt.
<?php
function encodeRand($str, $seed=1234567) {
mt_srand($seed);
$out = array();
for ($x=0, $l=strlen($str); $x<$l; $x++) {
$out[$x] = (ord($str[$x]) * 3) + mt_rand(350, 16000);
}
mt_srand();
return implode('-', $out);
}
function decodeRand($str, $seed=1234567) {
mt_srand($seed);
$blocks = explode('-', $str);
$out = array();
foreach ($blocks as $block) {
$ord = (intval($block) - mt_rand(350, 16000)) / 3;
$out[] = chr($ord);
}
mt_srand();
return implode('', $out);
}
$seed = 1249135;
echo "aaabbb:\n";
var_dump(encodeRand('aaabbb', $seed));
var_dump(decodeRand(encodeRand('aaabbb', $seed), $seed));
echo "\n\n";
echo "Katze:\n";
var_dump(encodeRand('Katze', $seed));
var_dump(decodeRand(encodeRand('Katze', $seed), $seed));
echo "\n\n";
echo "äöü:\n";
var_dump(encodeRand('äöü', $seed));
var_dump(decodeRand(encodeRand('äöü', $seed), $seed));
echo "\n\n";
echo "αЊᴁ₳:\n";
var_dump(encodeRand('αЊᴁ₳', $seed));
var_dump(decodeRand(encodeRand('αЊᴁ₳', $seed), $seed));
?>
aaabbb: string(31) "16257-6533-8419-14647-6719-9202" string(6) "aaabbb" Katze: string(26) "16191-6533-8476-14719-6728" string(5) "Katze" äöü: string(31) "16551-6734-8713-14899-7010-9472" string(6) "äöü" αЊᴁ₳: string(51) "16584-6773-8752-14767-7100-9448-8752-1357-8724-7471" string(10) "αЊᴁ₳"
3. encodeStrtr() / decodeStrtr()
Kernprinzip von encodeStrtr() ist es, jedes ASCII-Zeichen jeweils auf ein anderes ASCII-Zeichen abzubilden. Diese Zuordnung ist eindeutig, sodass zum Beispiel bei der Verschlüsselung „A” immer auf „+” und bei der Entschlüsselung „+” immer auf „A” abgebildet wird. Ist das Ausgangsalphabet und das Zielalphabet bekannt, dann kann diese Zuordnung sehr einfach über strtr($str, $ausgangsalphabet, $zielalphabet) erfolgen. Das Ausgangsalphabet entspricht wiederum allen Standard-ASCII-Zeichen in normaler Reihenfolge. Das Zielphabet kann gebildet werden, indem die Zeichen aus dem Ausgangsalphabet zufällig gemischt werden.
Um die Zeichen zufällig zu mischen wird hier die Funktion seededShuffle($arr, $seed) verwendet. Diese erwartet ein Alphabet als Array mit der Zuordnung Index=>Zeichen. Über eine foreach-Schleife iteriert es über alle Elemente des Arrays und weist jedem Element einen zufälligen neuen Index zu, der noch nicht belegt ist. Da dieser zufällige Index vom übergebenen Seed ($seed) abhängig ist, kann das „Mischen” später wieder umgekehrt werden. Zuletzt wird das Ausgabearray anhand der (zufälligen neuen) Schlüssel sortiert (siehe ksort()) und jeder Wert erhält wieder einen Schlüssel zwischen 0 und n (array_values()).
Damit das Ergebnis schwerer zu prognostizieren ist, führt die Funktion die Verschlüsselung nicht auf dem gesamten String durch, sondern nur auf einem Teilabschnitt. Der Ausgangsstring wird dazu in drei Teile $str1, $str2 und $str3 mit jeweils zufälligen Längen unterteilt. Nur $str2 wird verschlüsselt. So werden nicht ausnahmslos alle Zeichen im String auf bestimmte andere Zeichen abgebildet, sondern nur ein Teil davon. Dies ermöglicht es, die Funktion mehrmals hintereinander auszuführen bzw. zu iterieren. Andernfalls würde es bei mehreren Iterationen einfach reichen, dass Zielalphabet der letzten Iteration zu erzeugen und direkt alle Zeichen auf dieses Zielalphabet abzubilden. Alle Iterationen dazwischen wären nutzlos und könnten von einem Angreifer einfach übersprungen werden.
<?php
function encodeStrtr($str, $seed=1234567) {
$from = '';
$to = '';
for ($x=0; $x<256; $x++) {
$from[$x] = chr($x);
}
$to = $from;
$to = seededShuffle($to, $seed);
$from = implode('', $from);
$to = implode('', $to);
$len = strlen($str);
$start = mt_rand(0, $len-1);
$end = mt_rand($start, $len-1);
$str1 = substr($str, 0, $start);
$str2 = substr($str, $start, $end-$start);
$str3 = substr($str, $end);
return $str1 . strtr($str2, $from, $to) . $str3;
}
function decodeStrtr($str, $seed=1234567) {
$from = '';
$to = '';
for ($x=0; $x<256; $x++) {
$from[$x] = chr($x);
}
$to = $from;
$to = seededShuffle($to, $seed);
$from = implode('', $from);
$to = implode('', $to);
$len = strlen($str);
$start = mt_rand(0, $len-1);
$end = mt_rand($start, $len-1);
$str1 = substr($str, 0, $start);
$str2 = substr($str, $start, $end-$start);
$str3 = substr($str, $end);
return $str1 . strtr($str2, $to, $from) . $str3;
}
function seededShuffle($arr, $seed) {
mt_srand($seed);
$c = count($arr);
$out = array();
foreach ($arr as $val) {
$newKey = null;
while ($newKey === null) {
$newKey = mt_rand(0, $c * 10000);
if (isset($out[$newKey])) {
$newKey = null;
}
}
$out[$newKey] = $val;
}
ksort($out);
return array_values($out);
}
$seed = 1249135;
echo "aaabbb:\n";
var_dump(encodeStrtr('aaabbb', $seed));
var_dump(decodeStrtr(encodeStrtr('aaabbb', $seed), $seed));
echo "\n\n";
echo "Katze:\n";
var_dump(encodeStrtr('Katze', $seed));
var_dump(decodeStrtr(encodeStrtr('Katze', $seed), $seed));
echo "\n\n";
echo "äöü:\n";
var_dump(encodeStrtr('äöü', $seed));
var_dump(decodeStrtr(encodeStrtr('äöü', $seed), $seed));
echo "\n\n";
echo "αЊᴁ₳:\n";
var_dump(encodeStrtr('αЊᴁ₳', $seed));
var_dump(decodeStrtr(encodeStrtr('αЊᴁ₳', $seed), $seed));
?>
aaabbb: string(6) "aa�b" string(6) "aaabbb" Katze: string(5) "Ka~�e" string(5) "Katze" äöü: string(6) "ä�p̼" string(6) "äöü" αЊᴁ₳: string(10) "αЊ�lM��" string(10) "αЊᴁ₳"
4. addJunk() / removeJunk()
Im Gegensatz zu den vorherigen beiden Methoden erfolgt durch addJunk() keine Abbildung von bestimmten Zeichen auf andere Zeichen. Stattdessen werden — entsprechend des Namens — Abschnitte mit „Müll” eingefügt. Als „Müll” sind hier Zeichen anzusehen, die keinen Bezug zum ursprünglichen Text und dessen Inhalt haben. Sie werden an zufälligen Stellen im String eingefügt und beinhalten ebenso zufällige Zeichen. Dadurch wird es weiter erschwert, einfach nach Regelmäßigkeiten im Ergebnistext zu suchen, um die Verschlüsselung zu knacken.
Das Vorgehen ist verhältnismäßig einfach: Es wird über alle Zeichen im String iteriert. Bei jedem einzelnen Zeichen wird ein Zufallswert gebildet und mit einer übergebenen Wahrscheinlichkeit verglichen. Ist der Zufallswert kleiner als der Wert der Wahrscheinlichkeit, dann wird ein neuer Abschnitt Müll eingefügt. Die genaue Länge des Abschnitts liegt dabei zufällig zwischen einer Minimal- und einer Maximallänge, die ebenfalls an die Funktion übergeben werden kann.
Die Entschlüsselung erfolgt analog: Es wird über alle Zeichen iteriert und bei jedem Zeichen wieder geprüft, ob bei der Verschlüsselung Müll eingefügt worden ist (indem die selbe Wahrscheinlichkeitsberechnung wie bei der Verschlüsselung wiederholt wird). Falls ja, wird die Länge des Abschnitts bestimmt, ebenfalls über das selbe Verfahren wie bei der Verschlüsselung. Die Zeichen des Abschnitts werden dann übersprungen. Dabei ist nur zu berücksichtigen, dass die Zeichen des Abschnitts bei der Verschlüsselung zufällig generiert wurden und dadurch genauso viele neue Zufallszahlen generiert wurden, wie Zeichen im Abschnitt sind. Damit die Entschlüsselung mit den selben Zufallszahlen arbeiten kann wie die Verschlüsselung, muss auch bei der Entschlüsselung so oft der Zufallsgenerator abgefragt werden, wie Zeichen im Abschnitt sind — egal, ob diese Zeichen tatsächlich verwendet werden oder nicht.
<?php
function addJunk($str, $seed=1234567, $chance=0.6, $minlength=1, $maxlength=6) {
mt_srand($seed);
$chance = max(min(floatval($chance), 1.0), 0) * 100; // float zwischen 0 und 100
$out = array();
$countJunkAdded = 0;
for ($x=0, $l=strlen($str); $x<$l; ++$x) {
$isAdding = (mt_rand(0, 100) <= $chance ? true : false);
if ($isAdding) {
$length = mt_rand($minlength, $maxlength);
for ($j=0; $j<$length; ++$j) {
$out[$x + $countJunkAdded] = chr(mt_rand(0, 256));
$countJunkAdded++;
}
}
$out[$x+$countJunkAdded] = $str[$x];
}
return implode('', $out);
}
function removeJunk($str, $seed=1234567, $chance=0.6, $minlength=1, $maxlength=6) {
mt_srand($seed);
$chance = max(min(floatval($chance), 1.0), 0) * 100; // float zwischen 0 und 100
$out = array();
$countJunkAdded = 0;
for ($x=0, $l=strlen($str); $x<$l; ++$x) {
$hasAdded = (mt_rand(0, 100) <= $chance ? true : false);
if ($hasAdded) {
$length = mt_rand($minlength, $maxlength);
for ($j=0; $j<$length; $j++) {
mt_rand();
}
$x = $x + $length;
}
$out[$x+$countJunkAdded] = $str[$x];
}
return implode('', $out);
}
$seed = 1249135;
echo "aaabbb:\n";
var_dump(addJunk('aaabbb', $seed));
var_dump(removeJunk(addJunk('aaabbb', $seed), $seed));
echo "\n\n";
echo "Katze:\n";
var_dump(addJunk('Katze', $seed));
var_dump(removeJunk(addJunk('Katze', $seed), $seed));
echo "\n\n";
echo "äöü:\n";
var_dump(addJunk('äöü', $seed));
var_dump(removeJunk(addJunk('äöü', $seed), $seed));
echo "\n\n";
echo "αЊᴁ₳:\n";
var_dump(addJunk('αЊᴁ₳', $seed));
var_dump(removeJunk(addJunk('αЊᴁ₳', $seed), $seed));
echo "\n\n";
echo "012345678901234567890123456789012345678901234567890:\n";
var_dump(addJunk('012345678901234567890123456789012345678901234567890', $seed));
var_dump(removeJunk(addJunk('012345678901234567890123456789012345678901234567890', $seed), $seed));
?>
aaabbb:
string(16) "a�c�a�a�2�ab�1bb"
string(6) "aaabbb"
Katze:
string(15) "K�c�a�t�2�az�1e"
string(5) "Katze"
äöü:
string(16) "��c�����2�a��1ü"
string(6) "äöü"
αЊᴁ₳:
string(38) "��c�����2�a��1�R�k�� .���>� �� ׳"
string(10) "αЊᴁ₳"
012345678901234567890123456789012345678901234567890:
string(166) "0�c�1�2�2�a3�145R�k6� .�7�>� 8� �9�a��F0CHb�12�C3�4��:5|͋6d�>7��890��1��"l23 456789�=�.�p012t3��4��_5�l�+��6�l�{78]!��$h9x�ԍ�012�34�5S�8E6�7�8f9fv0"
string(51) "012345678901234567890123456789012345678901234567890"
5. Alle drei kombiniert
Im nächsten Beispiel werden zwei Funktionen — encodeCombined() und decodeCombined() — definiert, welche nacheinander die drei vorherigen Methoden ausführen. Die Funktionen bieten zusätzliche Parameter, um etwa einzelne Verfahren mehrmals auszuführen (jeweils mit wechselnden Schlüsseln/Seeds) und dadurch das Entschlüsseln zu erschweren. Zu beachten ist, dass gerade addJunk() bei zu großzügigen Parametern und mehreren Iterationen schnell sehr viel Müll zum String hinzufügt, wodurch der verschlüsselte Text entsprechend lang wird. Die Einstellungen sollten entsprechend vorsichtig gewählt werden.
<?php
function encodeRand($str, $seed=1234567) {
mt_srand($seed);
$out = array();
for ($x=0, $l=strlen($str); $x<$l; $x++) {
$out[$x] = (ord($str[$x]) * 3) + mt_rand(350, 16000);
}
mt_srand();
return implode('-', $out);
}
function decodeRand($str, $seed=1234567) {
mt_srand($seed);
$blocks = explode('-', $str);
$out = array();
foreach ($blocks as $block) {
$ord = (intval($block) - mt_rand(350, 16000)) / 3;
$out[] = chr($ord);
}
mt_srand();
return implode('', $out);
}
function encodeStrtr($str, $seed=1234567) {
$from = '';
$to = '';
for ($x=0; $x<256; $x++) {
$from[$x] = chr($x);
}
$to = $from;
$to = seededShuffle($to, $seed);
$from = implode('', $from);
$to = implode('', $to);
$len = strlen($str);
$start = mt_rand(0, $len-1);
$end = mt_rand($start, $len-1);
$str1 = substr($str, 0, $start);
$str2 = substr($str, $start, $end-$start);
$str3 = substr($str, $end);
return $str1 . strtr($str2, $from, $to) . $str3;
}
function decodeStrtr($str, $seed=1234567) {
$from = '';
$to = '';
for ($x=0; $x<256; $x++) {
$from[$x] = chr($x);
}
$to = $from;
$to = seededShuffle($to, $seed);
$from = implode('', $from);
$to = implode('', $to);
$len = strlen($str);
$start = mt_rand(0, $len-1);
$end = mt_rand($start, $len-1);
$str1 = substr($str, 0, $start);
$str2 = substr($str, $start, $end-$start);
$str3 = substr($str, $end);
return $str1 . strtr($str2, $to, $from) . $str3;
}
function seededShuffle($arr, $seed) {
mt_srand($seed);
$c = count($arr);
$out = array();
foreach ($arr as $val) {
$newKey = null;
while ($newKey === null) {
$newKey = mt_rand(0, $c * 10000);
if (isset($out[$newKey])) {
$newKey = null;
}
}
$out[$newKey] = $val;
}
ksort($out);
return array_values($out);
}
function addJunk($str, $seed=1234567, $chance=0.6, $minlength=1, $maxlength=6) {
mt_srand($seed);
$chance = max(min(floatval($chance), 1.0), 0) * 100; // float zwischen 0 und 100
$out = array();
$countJunkAdded = 0;
for ($x=0, $l=strlen($str); $x<$l; ++$x) {
$isAdding = (mt_rand(0, 100) <= $chance ? true : false);
if ($isAdding) {
$length = mt_rand($minlength, $maxlength);
for ($j=0; $j<$length; ++$j) {
$out[$x + $countJunkAdded] = chr(mt_rand(0, 256));
$countJunkAdded++;
}
}
$out[$x+$countJunkAdded] = $str[$x];
}
return implode('', $out);
}
function removeJunk($str, $seed=1234567, $chance=0.6, $minlength=1, $maxlength=6) {
mt_srand($seed);
$chance = max(min(floatval($chance), 1.0), 0) * 100; // float zwischen 0 und 100
$out = array();
$countJunkAdded = 0;
for ($x=0, $l=strlen($str); $x<$l; ++$x) {
$hasAdded = (mt_rand(0, 100) <= $chance ? true : false);
if ($hasAdded) {
$length = mt_rand($minlength, $maxlength);
for ($j=0; $j<$length; $j++) {
mt_rand();
}
$x = $x + $length;
}
$out[$x+$countJunkAdded] = $str[$x];
}
return implode('', $out);
}
function encodeCombined($str, $seed=1234567, $strtrIterations=100, $junkIterations=2, $junkChance=0.2, $junkMinlength=1, $junkMaxlength=3) {
$str = encodeRand($str, $seed);
for ($x=0; $x<$strtrIterations; ++$x) {
$str = encodeStrtr($str, $seed + (($x * 7) % 15251));
}
for ($x=0; $x<$junkIterations; ++$x) {
$str = addJunk($str, $seed + (($x * 7) % 13351), $junkChance, $junkMinlength, $junkMaxlength);
}
return $str;
}
function decodeCombined($str, $seed=1234567, $strtrIterations=100, $junkIterations=2, $junkChance=0.2, $junkMinlength=1, $junkMaxlength=3) {
for ($x=$junkIterations-1; $x>=0; --$x) {
$str = removeJunk($str, $seed + (($x * 7) % 13351), $junkChance, $junkMinlength, $junkMaxlength);
}
for ($x=$strtrIterations-1; $x>=0; --$x) {
$str = decodeStrtr($str, $seed + (($x * 7) % 15251));
}
$str = decodeRand($str, $seed);
return $str;
}
$seed = 1249135;
echo "aaabbb:\n";
var_dump(encodeCombined('aaabbb', $seed));
var_dump(decodeCombined(encodeCombined('aaabbb', $seed), $seed));
echo "\n\n";
echo "Katze:\n";
var_dump(encodeCombined('Katze', $seed));
var_dump(decodeCombined(encodeCombined('Katze', $seed), $seed));
echo "\n\n";
echo "äöü:\n";
var_dump(encodeCombined('äöü', $seed));
var_dump(decodeCombined(encodeCombined('äöü', $seed), $seed));
echo "\n\n";
echo "αЊᴁ₳:\n";
var_dump(encodeCombined('αЊᴁ₳', $seed));
var_dump(decodeCombined(encodeCombined('αЊᴁ₳', $seed), $seed));
echo "\n\n";
echo "012345678901234567890:\n";
var_dump(encodeCombined('012345678901234567890', $seed));
var_dump(decodeCombined(encodeCombined('012345678901234567890', $seed), $seed));
?>
aaabbb:
string(67) "��U�.^(Wo�l�U�ai8�™9�gR�z@C[9������>�\�t�59�?�ɐ��a��#��/2"
string(6) "aaabbb"
Katze:
string(61) "J��U�.^(6��l�iU]ai8Mn�9�gR�@C9+�����>�NĂ��9�G?�ɐ��a��8"
string(5) "Katze"
äöü:
string(67) "�>U�.^(�o�l� U�ai8™9�gR��@C[�������>��6�59 ?�ɐ��a��]��R2"
string(6) "äöü"
αЊᴁ₳:
string(97) "�*�U�.^(^�3l�Uai8�s�9�gR�6@C cf������>÷� ��9U�?]ɐ��a��wf�����/���0D�.J>{�j���{�o1� 1"
string(10) "αЊᴁ₳"
012345678901234567890:
string(211) "�g�U.^(��l�uU�ai8O֙9�gRL@C ��,����>ø�g��9[�?�ɐ��a�����?��f��4��]���>{��j�̮n�h�� ��T�{ ޕ��c�J�h7�� � +f"�\�$��`~�p �|ݩj�3tV������\��-�Ήov���Kˎ3܍m�߉J�za� i���$ih?<�-��rc�5"
string(21) "012345678901234567890"