Všeobecně používaná asymetrická šifra a Vernamovo XOR šifrování

Nebezpečí skryté ve všeobecně používané asymetrické šifře a bezpečný algoritmus používající Vernamovo XOR šifrování.

Šifrovací disk z občanské války v USAinternet

Pro obsáhlejší úvod do historického významu a technik šifrování zpráv doporučiji skvělou knihu Kniha kódů a šifer (podtitul Tajná komunikace od starého Egypta po kvantovou kryptografii, autor Simon Singh).

Kniha je žánrově na pokraji historické beletrie a technické literatury, kromě zajímavých technických myšlenek mne překvapila bohatost historie tohoto (z dnešního názvosloví) informační oboru a fascinovaly mne příběhy mnoha lidí, kteří, většinou bez jakéhokoliv uznání, zasvětili své osudy světu čísel a znaků (knihu považuji za natolik kvalitní a důležitou, že by měla patřit mezi povinnou četbu každého informatika).
V principu jde v šifrování o utajení nějakého obsahu pomocí tajné znalosti (kterou většinou můžeme nazvat šifrovacím klíčem) a kterou my, nebo adresát tajné zprávy použijeme k tomu, abychom si zprávu mohli opět přečíst.

Největším historickým problém šifrování vždy byla distribuce šifrovacích klíčů.
Ještě za druhé světové války bylo nutné pro jinak velice moderní šifrovací přístroj Enigma distribuovat vojenským jednotkám tisíce knih šifrovacích kódů, což bylo obrovskou administrativní zátěží a bezpečnostním rizikem.
Dnes je na internetu nejvíce používané asymetrické šifrování, u kterého je oddělen klíč pro šifrování a dešifrování zprávy, dešifrovací klíč se nemusí zveřejňovat a odpadá potřeba jeho distribuce.

Pro ilustraci principů asymetrického šifrování si vypůjčím (mírně upravenou) definici z české Wikipedie:
"Analogií pro pochopení výhod asymetrického šifrování je příklad, ve kterém si Alice a Bob posílají zprávy pomocí veřejné pošty -  Alice posílá utajenou zprávu Bobovi a očekává utajenou odpověď .
Při použití symetrické kryptografie Alice vloží zprávu do schránky a zamkne pomocí visacího zámku, ke kterému má klíč. Schránku poté pošle poštou Bobovi, ten ji otevře použitím kopie Aliččina klíče a přečte si zprávu. Bob pak může použít stejný zámek pro odeslání jeho odpovědi.
U asymetrické kryptografie má každý svůj visací zámek. Nejdříve Alice požádá Boba, aby jí poslal otevřený zámek bez klíče poštou. Poté jím Alice zamkne zprávu do schránky a tu pošle Bobovi. Bob potom může otevřít zámek svým klíčem a přečíst si zprávu od Alice. K poslání odpovědi musí mít Aliččin otevřený zámek, kterým zamkne schránku a pošle ji zpátky Alici.
Největší výhodou tak je, že Alice ani Bob nepotřebují posílat kopii jejich klíče. Tímto se zamezí vytvoření kopie klíče někým třetím během přenosu a odposlouchávání všech následně poslaných zpráv mezi Alicí a Bobem. Nepotřebují tedy věřit poště tolik jako v prvním případě. Navíc, pokud by Bob někomu dovolil si zkopírovat jeho klíč, tak by byly kompromitovány pouze zprávy od Boba, ale všechny zprávy od Alice by zůstaly utajené.
V dalším případě mají Bob a Alice každý svůj zámek. Nejdříve Alice vloží zprávu do schránky a zamkne ji svým klíčem, který má jen ona. Potom schránku poštou pošle Bobovi. Ten schránku zamkne i svým zámkem a pošle jí zpátky Alici. Alice odebere svůj zámek a schránku s jedním zámkem pošle Bobovi, který tento svůj zámek otevře svým klíčem. Toto je ovšem možné pouze pokud je použitá šifra komutativní. Což je taková šifra, ve které můžeme zaměnit pořadí šifrování a dešifrování: A*B*C = A*C*B = C*B*A."
Riziko asymetrického šifrováním ale spočívá v tom, že je založeno ma matematických funkcích, které lze testovat na správnost výsledku a ke kterým lze hledat neznámé šifrovací klíče kombinatorickým testováním, při němž zkoušíme všechny možné číselné kombinace, než najdeme kombinaci, která slouží jako klíč pro čtení. Opět citace z téhož odkazu Wikipedie:

"Na rozdíl od Vernamovy šifry se žádná metoda asymetrické kryptografie neukázala jako bezpečná při použití nekonečného výpočetního výkonu. Důkazy bezpečnosti těchto metod tedy počítají s omezeným výpočetním výkonem a říkají například, že „metoda je nerozluštitelná pomocí osobního počítače za 1000 let“, nebo „tento algoritmus je bezpečný, pokud nedojde k objevení lepší metody pro faktorizaci“."
S aktuálním nebezpečím prolomení asymetrického šifrování souvisí trendy využití kvantových počítačů, v kterých je v jednom okamžiku možné pracovat se všemi kombinatorickými stavy určité množiny čísel (znaků) viz odkaz. Z toho vyplývá, že pro kvantové počítače není velký problém dnešní asymetrické šifrování překonat, zajímavá diskuze například zde.
Z Knihy kódů a šifer je patrná ještě jedna zajímavá skutečnost: to, co umí v oblasti (de)šifrování tajné vládní a vojenské laboratoře, se veřejnost dozvídá přibližně s odstupem 20ti až 30ti let.

Je tedy možné, že by již dnes byly tajné služby schopny překonat běžně používané šifrování ?

Pokud ano, vzhledem k náročnosti operace a případným omezeným technickým kapacitám bych se nebál ohrožení běžné komunikace či nákupů na internetu, ale principiálně bych tuto možnost nevylučoval.

Nejjednodušší a přitom nerozluštitelné šifrování XOR - Vernamova šifra
Bez detailnějšího popisu opět s odkazem na článek Wikipedie, Vernamova šifra - reverzibilní kódování metodou XOR - je jedním z nejspolehlivějších a nejjednodušších šifrování.

Logická / bitová operace XOR (eXclusive OR) označí výsledek za pravdu (jedničku) v případě, že vstup A nebo B je pravdou, nikoliv ale když je pravdou A i B.

Pro binární čísla například

1001 XOR 1110 = 0111

XOR má zajímavou vlastnost reverzibilního dekódování, kdy

(A XOR B) XOR B = A

tedy

(1001 XOR 1110) XOR 1110 = 1001

kdy dvojitým provedením stejné XOR operace získáme původní číslo.

Proč je kódování XOR nerozluštitelné ?

Pokud máme transformaci

(Tajná zpráva) XOR (Tajný klíč) = (Veřejný šifrovaný text)

a hledáme Tajnou zprávu, kombinatorické testování Tajného klíče nám nepomůže,
protože nemáme jak otestovat validitu (správnost) tajného klíče ani rozšifrované tajné zprávy a vždy najdeme nějaký nesprávný tajný klíč, který nám transformuje šifrovaný text do jakékoliv (nesprávné) podoby tajné zprávy (vše při předpokladu stejné délky zpráv a klíčů, tento předpoklad pro zjednodušení opomíjím).

Například máme-li

"Toto je tajná zpráva" XOR (Tajný klíč) = "Toto je zašifrovaná zpráva"

vždy najdeme takový (nesprávný) tajný klíč, který nám dá výsledek

"Toto je zašifrovaná zpráva" XOR (Špatný tajný klíč) = "Toto není původní tajná zpráva"

"Toto je zašifrovaná zpráva" XOR (Další špatný tajný klíč) = "Toto taky není původní tajná zpráva"

Můžeme tedy najít "nekonečně" mnoho klíčů vracejících z jedné zašifrované zprávy zdánlivě smysluplně rozšifrovaná data (texty),  nemůžeme ale ověřit, který z těchto výsledků je ten správný.

doplnění 9.3.2011: děkuji za komentář v diskuzi, za celkem amatérský omyl se omlouvám,  dále popisovaná úvaha je neplatná. -----------------------------------------------------------------------------------------------------------

Aplikace XOR pro asymetrické šifrování

Ještě jednou poštovní analogie varianty asymetrického šifrování:

"V dalším případě mají Bob a Alice každý svůj zámek. Nejdříve Alice vloží zprávu do schránky a zamkne ji svým klíčem, který má jen ona. Potom schránku poštou pošle Bobovi. Ten schránku zamkne i svým zámkem a pošle jí zpátky Alici. Alice odebere svůj zámek a schránku s jedním zámkem pošle Bobovi, který tento svůj zámek otevře svým klíčem. Toto je ovšem možné pouze, pokud je použitá šifra komutativní. Což je taková šifra, ve které můžeme zaměnit pořadí šifrování a dešifrování: A*B*C = A*C*B = C*B*A."

Právě XOR může být tímto komutativním šifrováním využitelným v popsaném postupu.
Postup šifrování:

• Alice má zprávu A, kterou chce tajně poslat Bobovi.
• Alice si vytvoří náhodný klíč KA, nejlépe stejné velikosti, jakou je zpráva, klíčem provede XOR operaci nad zprávou A, vznikne šifra S1
• Bob obdrží šifru S1, vytvoří si svůj náhodný klíč KB, provede nad S1 operaci XOR se svým klíčem KB, vznikne šifra S2, tu Bob zašle zpět Alici
• Alice obdrží šifru S2, svým klíčem KA opět provede nad S2 operaci XOR, vznikne šifra S3, kterou zašle zpět Bobovi. Svůj klíč KA nyní může Alice zapomenout.
• Bob obdrží šifru S3, nad kterou provede XOR s KB, výsledkem je původní zpráva A. Bob může svůj náhodný klíč KB zahodit, víckrát ho nepoužije.
• Pokud si Alice s Bobem posílají další zprávu, každý si vytvoří nové náhodné šifrovací klíče.

Co se stalo:

• Alice poslala Bobovi tajnou zprávu, ten si ji přečte, přitom Alice i Bob mají svůj tajný klíč, který nikomu nepůjčí a nikam ho nemusí posílat
• Zprávu si musí poslat dvakrát, ale nakonec má Bob původní tajný text
• Použité binární XOR kódování je v principu velice jednoduché a přitom nerozluštitelné

Nevýhody:

• Zpráva se mezi Alicí a Bobem musí poslat 2x, znamená to dvojnásobnou náročnost datového přenosu a aktivní účast příjemce na komunikaci.
• Klasické asymetrické šifrování umožňuje zaslat příjemci šifrovanou zprávu (například emailem), příjemce je v tu chvíli pasivní, o zaslání zprávy nemusí nic vědět, až někdy v budoucnu si ji přečte.
• Popsaný postup je vhodný ke komunikaci mezi dvěmi stranami, není vhodný například pro archivování dat

Bezpečnost řešení:

Opět citace Wikipedia:
"Binární varianta je obzvláště citlivá na opakované použití klíče. Důvodem je následující vlastnost operace XOR:(A XOR X) XOR (B XOR X) = A XOR B. Když má tedy útočník v ruce dvě zprávy šifrované týmž klíčem a provede s nimi XOR, dostane XOR dvou původních zpráv a zbaví se veškeré náhodnosti, která spočívala v klíči a která dává šifře její sílu. Statistická kryptoanalýza mu pak už docela lehce umožní zprávy přečíst."

V popsaném postupu se sice operace XOR provede dvakrát se stejným klíčem, (z pohledu Alice) poprvé nad tajnou zprávou, podruhé nad šifrovanými daty S2. Protože druhé šifrování je provedeno nad šifrovanými ("náhodnými") daty, nelze nad případně získaným XORem S1 a S2 provést statistickou kryptoanalýzu, data si zachovávají náhodnou charakteristiku, postup je dle mého svědomí zcela bezpečný.

Shrnutí

Je tedy používaná klasická asymetrická šifra bezpečná ?

Věřím, že pro běžné účely je ještě (snad) bezpečná dostatečně, ne však pro budoucnost, a pokud bych měl zodpovědnost nad strategicky bezpečnou komunikací, pak bych raději věřil popsanému dvojitému XOR šifrování.
Bude někdy šifrovaná komunikace opravdu bezpečná ?

Možnost teoreticky neprolomitelného šifrování v podobě "nepodmíněné bezpečnosti" zde existuje, její uplatnění v běžné praxi je ale rozhodně pro nejbližší desetiletou budoucnost ještě nereálné. Ani z politického hlediska asi nebude vůle státních aparátů principiálně neprolomitelné šifrování zpřístupnit široké (a z hlediska státu nebezpečné) veřejnosti, stačí připomenout první veřejnou implementaci asymetrické šifry a jejího autora Philla Zimmermanna, kterého USA vláčely za zpřístupnění šifry po soudech až do roku 1996.

Odvolání (disclaimer)

Za popsaným algoritmem si svými znalostmi a svědomím stojím a prohlašuji, že mi, při předpokladu zachování utajení šifrovacích klíčů a při jejich výměně pro zaslání každé nové zprávy, není známa žádná jeho bezpečnostní slabost. Zároveň si ale uvědomuji, že celá (nejen technická) historie je dlážděna omyly, a pokud mi někdo výše popsaný algoritmus vyvrátí, nebudu to považovat za osobní útok, naopak takový člověk by si zasloužil respekt.

Praktická ukázka

Krátká praktická ukázka algoritmu (Java, GWT) bezpečného přenosu dat mezi klientem web aplikace a serverem:

public static byte[] XOR(byte[] data, byte[] key) {
byte[] result = new byte[data.length];
int n = 0;
for (int i = 0; i < data.length; i++) {
byte a = data[i];
byte b = key[n];
byte c = (byte) (a ^ b); //XOR
result[i] = c;
n++;
if (n >= key.length)
n = 0;
}
return result;
}

//////////// klient:

void submitLogin(String password, String username) {
MD5 md5 = new MD5();
md5.update(username);
md5.update(password);
String hash = username + "|" + MD5.asHex(md5.finalizeHash());
byte[] data = hash.getBytes();
final byte[] key = new byte[data.length];
//create random key
for (int i = 0; i < key.length; i++) {
key[i] = (byte) (Random.nextInt(256));
}
final AsyncCallback<UserAccessClient> callbackLogin2 = new AsyncCallback<UserAccessClient>() {
public void onFailure(Throwable caught) {
SC.warn(caught.toString());
}
public void onSuccess(UserAccessClient result) {
if (result != null) {
Utils.redirectToApplicationPage();
} else {
//INVALID LOGIN
SC.warn(LoginEntryPoint.this.constants.loginError(), invalidLoginCallback);
}
}
};
final AsyncCallback<byte[]> callbackLogin1 = new AsyncCallback<byte[]>() {
public void onFailure(Throwable caught) {
SC.warn(caught.toString());
}
public void onSuccess(byte[] result) {
byte[] encryptedData = XOR(result, key);
//second message transfer
personalisationService.validateToken2(encryptedData, callbackLogin2);
}
};
data = XOR(data, key);
//first message transfer
personalisationService.validateToken1(data, callbackLogin1);

} //end - submit login

//////////// server:

public byte[] validateToken1(byte[] token) {
if (token == null)
return null;
// create session
HttpSession session = getThreadLocalRequest().getSession(true);
Random rnd = new Random();
byte[] key = new byte[token.length];
rnd.nextBytes(key);
session.setAttribute("secureKey", key); //$NON-NLS-1$
byte[] data = XOR(token, key);
return data;

}
public UserAccessClient validateToken2(byte[] token) {
if (token == null)
return null;
// create session
HttpSession session = getThreadLocalRequest().getSession(false);
if (session == null)
return null; // session not supported ?
byte[] key = (byte[]) session.getAttribute("secureKey");
if (key == null) return null;
session.removeAttribute("secureKey");
byte[] data = XOR(token, key);
//this is the decrypted message
String signInInfo = new String(data);
//validate user
boolean userValidated = false;
...
if(userValidated) {
return userInfo;
} else {
return null;
}

}