Veiligheid Vigenère encryptie implementatie

[wizzkizz]

Voor een programmeervak moest ik een implementatie maken van de Vigenère versleuteling. So far so good, dus ik een mooie implementatie gemaakt. Echter, de Vigenère versleuteling is al redelijk oud en het zwakste punt is de sleutellengte. Als die eenmaal bekend is (oa. mogelijk met de Kasiski test of de Friedman-test bijvoorbeeld), is het mbv frequentieanalyse mogelijk de versleuteling terug te brengen tot een Ceasar cipher, die gemakkelijk te kraken is, gesteld dat de taal van de plaintext bekend is.

Nu verloopt het coderen in mijn progje met een tussenstap, de plaintext wordt eerst in BASE64 omgezet, om ervoor te zorgen dat de plaintext alle informatie kan bevatten die je maar kunt bedenken en je met een relatief kleine tabula recta aan de slag kan (een 63*63 matrix). Daarnaast kun je kiezen tussen de "originele" versleuteling of de "Variant Beauford" (waarbij het decryptie-proces gebruikt wordt om te encrypten en het encryptieproces om te decrypten).

Om gebruikers toch een goede sleutellengte te bieden bij een minimaal wachtwoord, heb ik het volgende gedaan: allereerst wordt het wachtwoord gehashed mbv SHA512, waardoor je een string van een vaste lengte krijgt. Omdat dit de sleutellengte vast maakt, moet je dat niet willen. Daarom wordt de uiteindelijke sleutel als volgt in elkaar gedraaid:

Visual Basic:

        ' OK, we now do know the password has 64 bytes. Now lets make it somewhat harder to do a succesful attack on the encrypted text by making the length of the 
        ' password variable (ranging from 31 to 136 chars).
        For intCounter = 0 To intSecretLength
            ' Sorry, passwords with a length of 16 chars or more makes no sense in this way (only for the hash!)
            If (intCounter >= 16) Then Exit For

            ' Determine starting position
            intStart = intCounter * (17 - intCounter)

            ' Make sure we can take the substring
            If ((intStart + (16 - intCounter)) >= strSecret.Length) Then
                intStart = intCounter * 3
            End If

            strSecretSecured += strSecret.Substring(intStart, 16 - intCounter)
        Next

De uiteindelijke sleutellengte is dus afhankelijk van de lengte van het opgegeven wachtwoord en varieert van 31 tekens (bij wachtwoord van 1 teken) tot 136 tekens (bij een wachtwoord van 16 of meer tekens).

Nu mijn vraag:
In hoeverre is mijn Vigenère cipher bestand tegen cryptoanalyse (gesteld dat mijn implementatie van het Vigenère cipher bugvrij is)? Ik heb mijn best gedaan om het lastig te maken, maar ben geen cryptoanalist of briljant wiskundige, dus wellicht heb ik heel veel dingen over het hoofd gezien.
Zowel het achterhalen van de sleutellengte als een frequentie analyse lijken mij behoorlijk lastig. Er is immers geen sprake van een natural language waar je een een frequentie analyse van kunt gebruiken, maar een BASE64 encoding van mogelijk binaire bestanden of platte tekst met allerlei leestekens etc.
Uiteraard is het niet bedoeld om NSA-safe te zijn, maar als ik toch een opdracht moet maken, kan ik het maar net zo goed goed uitvoeren ook

Iemand met wat meer verstand van crypto die hier iets zinnigs over kan zeggen?

[RobIII]

Lijkt me meer iets voor SEA (Waar hoort mijn topic?)
PRG >> SEA

wizzkizz schreef op maandag 27 april 2009 @ 12:09:
Om gebruikers toch een goede sleutellengte te bieden bij een minimaal wachtwoord, heb ik het volgende gedaan

Een (korte) sleutel levert toch altijd dezelfde hash op? Dan kan 'ie nog wel een miljoen bits zijn; de basis is nog steeds een sleutel van (bijv.) 3 tekens. Je legt dus, IMHO, schijnveiligheid neer.

[ Voor 60% gewijzigd door RobIII op 27-04-2009 12:15 ]

[wizzkizz]

RobIII schreef op maandag 27 april 2009 @ 12:13:
Lijkt me meer iets voor SEA (Waar hoort mijn topic?)
PRG >> SEA

[...]

Een (korte) sleutel levert toch altijd dezelfde hash op? Dan kan 'ie nog wel een miljoen bits zijn; de basis is nog steeds een sleutel van (bijv.) 3 tekens. Je legt dus, IMHO, schijnveiligheid neer.

Als de aanvaller alleen over de versleutelde tekst beschikt is het geen schijnveiligheid, wel als het algoritme bekend is. Als zeg maar een e-mail onderschept wordt die alleen bestaat uit mijn versleutelde tekst, dan is het hebben van een key van tig bits beter dan van maar een paar bits. Als ze weten hoe van het oorspronkelijke wachtwoord een key gemaakt wordt, heb je inderdaad gelijk dat het geen toegevoegde waarde heeft.

[edit]
Is het security-by-obscurity? Misschien, want het helpt niet echt tegen een brute-force aanval ofzo. De enige reden waarom het toegevoegd is, is omdat gebruikers vaak onveilige wachtwoorden gebruiken. Mocht iemand een versleuteld bericht in het wild aantreffen, dan is deze security-by-obscurity een extra beveiligingslaag indien de aanvaller niet weet op welke manier de key bepaald is. Mocht het algoritme bij de aanvaller bekend zijn, dan hangt de veiligheid af van het wachtwoord dat de gebruiker heeft gekozen. Dus in bepaalde situaties kan het een extraatje bieden, in andere situaties is het een waste of cpu-cycles.

[ Voor 26% gewijzigd door wizzkizz op 27-04-2009 20:00 ]

[Hydra]

wizzkizz schreef op maandag 27 april 2009 @ 19:54:
Is het security-by-obscurity? Misschien, want het helpt niet echt tegen een brute-force aanval ofzo. De enige reden waarom het toegevoegd is, is omdat gebruikers vaak onveilige wachtwoorden gebruiken. Mocht iemand een versleuteld bericht in het wild aantreffen, dan is deze security-by-obscurity een extra beveiligingslaag indien de aanvaller niet weet op welke manier de key bepaald is. Mocht het algoritme bij de aanvaller bekend zijn, dan hangt de veiligheid af van het wachtwoord dat de gebruiker heeft gekozen. Dus in bepaalde situaties kan het een extraatje bieden, in andere situaties is het een waste of cpu-cycles.

Het hele idee achter dat "security by obscurity" geen security is, is juist dat het schijnveiligheid is. Ik kan ook wel een simpel XOR-algorithme implementeren dat aan de hand van een sleutel van 4 bytes elke tekst in rotzooi omzet, maar zogauw je het algorithme weet is het kraken een eitje. Je moet er bij encryptie ALTIJD vanuit gaan dat het algoritme voor iedereen in te zien is. Als de berichten zo geheim zijn dat mensen moeite gaan doen de inhoud te achterhalen, dan is je algorithme in no time bekend.

[wizzkizz]

Hydra schreef op dinsdag 28 april 2009 @ 11:23:
[...]


Het hele idee achter dat "security by obscurity" geen security is, is juist dat het schijnveiligheid is. Ik kan ook wel een simpel XOR-algorithme implementeren dat aan de hand van een sleutel van 4 bytes elke tekst in rotzooi omzet, maar zogauw je het algorithme weet is het kraken een eitje. Je moet er bij encryptie ALTIJD vanuit gaan dat het algoritme voor iedereen in te zien is. Als de berichten zo geheim zijn dat mensen moeite gaan doen de inhoud te achterhalen, dan is je algorithme in no time bekend.

Ja daar heb je gelijk in, maar het versleutelingsalgoritme is hier niet op gebaseerd, alleen de bepaling van de sleutel. Het versleutelen gebeurt met behulp van het Vigenère cipher, Daar is niets geheims aan, dat is een publiekelijk bekende polyalfabetische substitutie uit 1553 .

Het idee is dat zelfs een wachtwoord van bijvoorbeeld 6 tekens een sleutel van 91 tekens oplevert. Nee, dat is niet nuttig als iemand het programmaatje heeft. Ja, dat is wel nuttig als iemand je vercijferde tekst tegenkomt en deze probeert te kraken. Beveiliging is een idee van gelaagdheid. Dit is alleen maar een extra laagje, dat in bepaalde gevallen wel en in andere gevallen geen extra veiligheid bied.

En omdat het in bepaalde gevallen juist wel een extra beveiliging biedt, lijkt het me nuttig om het toe te passen. Een vastbesloten aanvaller laat zich hier natuurlijk niet door weerhouden, dat snap ik prima. Maar voor huis-tuin-en-keukengebruik lijkt het me wel nuttig.

offtopic:
Het is geen beveiligingsprogramma oid dat ik ga aanbieden, alleen maar een schoolopdracht waarmee ik op deze manier extra punten hoop te krijgen

[ Voor 2% gewijzigd door wizzkizz op 28-04-2009 11:46 . Reden: iets meer info over Vigenère cipher ]

[Hydra]

Hmm. Ik vind het een beetje een tussengeval. Je probleem is dat je sleutel te kort is. Je lost het probleem niet op, maar maakt het wel moeilijker te herkennen. Als je in je opdracht aangeeft dat het een "truukje" is om het wat moeilijker te maken, maar niet de veiligheid verhoogd, zie ik geen probleem het mee te nemen.

Andere opmerking trouwens: vind je het een goed idee om je tekst te base-64 encoden? Hoe minder verschillende characters er in je plaintext zitten, hoe makkelijker een bericht te kraken is.

[leuk_he]

Echter, de Vigenère versleuteling is al redelijk oud en het zwakste punt is de sleutellengte. Als die eenmaal bekend is (oa. mogelijk met de Kasiski test of de Friedman-test bijvoorbeeld)

Als ik het goed begrijp is je methode om de lengte van de key te veranderen vast. Dus er zijn niet 104 keylengtes (wat niet eens erg veel is) maar 16 lengtes. Dus je algorithme is er niet veiliger door geworden. (even aangenomen dat het algoritme geanalyseerd mag wroden).

Als je de lengte van de uiteindelijk key niet alleen van de lengte, maar ook van de inhoud van de secretkey laat afhangen ben je wel een factor ~16 veiliger. (niet spectaculair, maar toch).

Omzetten naar Base64 is een 1-> 1 transformatie die iemand die het analyseer 1 op 1 ongedaan kan maken, dus niet de veiligheid vergroot. (door obscurity, ja, maar die disucssie is hierboven al aangezwengeld). Wat extra xor transformaties zouden hetzelfde bereiken denk ik.

Wat wel je je veiligheid vergroot is je data eerst comprimeren voor encrypty, want in een goede compressie is de data wel willekeurig verdeeld, en dat maakt analyse veel moeilijker. Wel opletten dat je niet een encryptie methode gebruikt waar je header standaard is, want dan geef je een stuk van plaintext meteen al weg.

Overigens betwijfel ik dat de cipher echt veilig is te krijgen, deze cipher was enigszins veilig in de tijd van handmatige ciphers, in het computertijdperk tellen andere criteria.

voor veilige ciphers ga je uiteraard bij bestaande implemntaties van moderen ciphers te rade maar dat was niet je punt.

[Rukapul]

Dat de sleutellengte niet voorspelbaar mag zijn neem ik even voor waar aan.

Het onvoorspelbaar maken van de sleutellengte op deze wijze is niets meer of minder dan security by obscurity. De security neemt ook niet toe omdat de lengte van de sleutel nog steeds maar 16 mogelijkheden kent waardoor een aanval slechts een orde grootte meer rekenkracht kost gegeven bekendheid van de obfuscatie.

Het hele probleem doet me denken aan key scheduling zoals dat ook bij moderne ciphers (met Feistel structuur) voorkomt. Alle bitjes reorganiseren en goed zetten voor input in de diverse rondes van het cipher

[wizzkizz]

Hydra schreef op dinsdag 28 april 2009 @ 11:53:
Hmm. Ik vind het een beetje een tussengeval. Je probleem is dat je sleutel te kort is. Je lost het probleem niet op, maar maakt het wel moeilijker te herkennen. Als je in je opdracht aangeeft dat het een "truukje" is om het wat moeilijker te maken, maar niet de veiligheid verhoogd, zie ik geen probleem het mee te nemen.

Andere opmerking trouwens: vind je het een goed idee om je tekst te base-64 encoden? Hoe minder verschillende characters er in je plaintext zitten, hoe makkelijker een bericht te kraken is.

Qua veiligheid heb je gelijk, maar anders wordt de tabula recta veel groter, als snel een 255*255 matrix. Oké, moet opzich geen probleem zijn natuurlijk, maar het geheugengebruik moet ook zo minimaal mogelijk zijn. En het lijkt mij dat het een extra bescherming biedt tegen een frequenty-analyse, maar dat is puur gevoelsmatig en heb ik niet wiskundig onderzocht (dat gaat me veel te ver voor een eenvoudige programmeeropdracht). Maar mijn eerste reden hiervoor was dus om zo alle mogelijke karakters (incl. non-printable) te ondersteunen met een minimale tabula recta en niet extra veiligheid.

leuk_he schreef op dinsdag 28 april 2009 @ 12:04:
[...]


Als ik het goed begrijp is je methode om de lengte van de key te veranderen vast. Dus er zijn niet 104 keylengtes (wat niet eens erg veel is) maar 16 lengtes. Dus je algorithme is er niet veiliger door geworden. (even aangenomen dat het algoritme geanalyseerd mag wroden).

Als je de lengte van de uiteindelijk key niet alleen van de lengte, maar ook van de inhoud van de secretkey laat afhangen ben je wel een factor ~16 veiliger. (niet spectaculair, maar toch).

Omzetten naar Base64 is een 1-> 1 transformatie die iemand die het analyseer 1 op 1 ongedaan kan maken, dus niet de veiligheid vergroot. (door obscurity, ja, maar die disucssie is hierboven al aangezwengeld). Wat extra xor transformaties zouden hetzelfde bereiken denk ik.

Wat wel je je veiligheid vergroot is je data eerst comprimeren voor encrypty, want in een goede compressie is de data wel willekeurig verdeeld, en dat maakt analyse veel moeilijker. Wel opletten dat je niet een encryptie methode gebruikt waar je header standaard is, want dan geef je een stuk van plaintext meteen al weg.

Overigens betwijfel ik dat de cipher echt veilig is te krijgen, deze cipher was enigszins veilig in de tijd van handmatige ciphers, in het computertijdperk tellen andere criteria.

voor veilige ciphers ga je uiteraard bij bestaande implemntaties van moderen ciphers te rade maar dat was niet je punt.

Ik moet inderdaad roeien met de riemen die ik heb De opdracht is een computerimplementatie te maken van deze handmatige cipher, dus qua veiligheid ben je dan sowieso beperkt. Je hebt wel een punt met dat er maar 16 mogelijke sleutellengtes zijn, dat was me even ontgaan Daar ga ik iets moois op proberen te verzinnen.

Die BASE64 is niet primair bedoeld voor veiligheid, zie ook hierboven. Die compressie ga ik even over nadenken, zou wel een nuttige toevoeging zijn. Moet wel even informeren bij de docent wat het zou uitmaken qua cijfer, anders is het de moeite niet waard. Maar het aandragen bij de bespreking alleen al toont aan dat ik ervan op de hoogte ben (gebracht nu dus door u, dank u)

Tot zover iedereen bedankt voor het aandragen van info die ik kan gebruiken bij het bespreken van de opdracht (plus waarvoor ik tegenargumenten moet bedenken cq. aanpassen in mn programma). Dingen die hier nog niet genoemd zijn, zijn uiteraard nog van harte welkom.

[Hydra]

wizzkizz schreef op dinsdag 28 april 2009 @ 13:06:
Qua veiligheid heb je gelijk, maar anders wordt de tabula recta veel groter, als snel een 255*255 matrix. Oké, moet opzich geen probleem zijn natuurlijk, maar het geheugengebruik moet ook zo minimaal mogelijk zijn. En het lijkt mij dat het een extra bescherming biedt tegen een frequenty-analyse, maar dat is puur gevoelsmatig en heb ik niet wiskundig onderzocht (dat gaat me veel te ver voor een eenvoudige programmeeropdracht). Maar mijn eerste reden hiervoor was dus om zo alle mogelijke karakters (incl. non-printable) te ondersteunen met een minimale tabula recta en niet extra veiligheid.

255*255 is 64k, da's niks. Je maakt analyse het moeilijkst door je plaintext 'random' te maken (door compressie bijvoorbeeld, maar je kunt ook meerdere mogelijkheden aan elk plaintext character te geven) en dus niet maar 64 mogelijke characters te hebben.

[leuk_he]

[b][message=31865605,noline]wizzkizz schreef op dinsdag 28 april 2009 @ [...]
Die BASE64 is niet primair bedoeld voor veiligheid,

Je kunt de cipher net zo goed toepassen op een matix van 255 karakters ipv 26 of 64. Als je de gencodeerde uitkomt moet printen is base64 wellicht wel weer handig omdat je geen unprintable karakter wilt afdrukken. Maar het is niet de essentie van de opdracht lijkt me.

[MSalters]

Ik denk dat we het probleem missen. Er zijn in dit geval twee aanvallen denkbaar. De eerste is een aanval tegen het wachtwoord; een tweede is tegen de Vigenère sleutel. Het achterhalen van de sleutellengte is volstrekt irrelevant in dit geval; dat levert je namelijk geen informatie op. Je weet nog steeds niet hoe lang het wachtwoord was dat gebruikt werd als input voor de hash.

Juist de tussenstap maakt he nu onveilig. Het injecteert informatie over de wachtwoordlengte in de sleutellengte, en daarmee is een groot aantal mogelijke wachtwoorden uitgesloten als je de sleutellengte weet. Bijvoorbeeld: als je een sleutellengte van 31 vindt, dan brute-force je alle wachtwoorden van lengte 1.

Een triviale stap die de veiligheid wel verbetert is salten. Je kiest een random suffix met lengte N die je append aan je password, en prepend dat voor je ciphertext. Bij decryptie pak je die N bytes en plak je ze weer aan je password. Dit zorgt ervoor dat je geen pre-calculated SHA256 tables meer kunt gebruiken.

code:

#Encryptie
salt[4] = RAND(256), RAND(256), RAND(256), RAND(256)
sleutel = SHA256(password + salt)
output = salt + vigenere_enc(input, sleutel)
#Decryptie
salt[4] = substring(input,0,4)
sleutel = SHA256(password + salt)
output = vigenere(substring(input,4,end))

[wizzkizz]

Oké, het lijkt me sowieso duidelijk dat ik de mogelijke input ga beperken, zodanig dat alle geaccepteerde tekens binnen de 255*255 matrix vallen en de BASE64 codering laat ik dan vallen.
Verder ga ik ervoor zorgen dat de lengte van het wachtwoord niet uit de sleutellengte is af te leiden, hetzij door het gebruik van een methode om de tekst van het wachtwoord te gebruiken om de mogelijke "gaps" op te vullen en de volledige lengte van het wachtwoord te gebruiken (waarbij sleutellengte = x zoveel mogelijk uitkomsten kent voor lengte wachtwoord bij sleutellengte y), hetzij door het huidige mechanisme te laten vallen en de gebruiker van een zwak wachtwoord te laten stikken

quote: MSalters

Het achterhalen van de sleutellengte is volstrekt irrelevant in dit geval; dat levert je namelijk geen informatie op

De lengte van de sleutel is juist een vereiste om een succesvolle aanval te plegen op de Vigenère sleutel, dus daarom is het wel relevant. Dat was ook juist de reden dat ik geen gebruik wilde maken van alleen het hashen van het password, want dan is de sleutellengte altijd bekend. Als ik hier de plank missla, dan hoor ik het graag en zal ik alsnog gaan salten om aanvallen met rainbow-tables te weerstaan.

quote: leuk_he

Je kunt de cipher net zo goed toepassen op een matix van 255 karakters ipv 26 of 64. Als je de gencodeerde uitkomt moet printen is base64 wellicht wel weer handig omdat je geen unprintable karakter wilt afdrukken. Maar het is niet de essentie van de opdracht lijkt me.

Één van de eisen waaraan het programma moet voldoen, is het kunnen inlezen van bestanden. Omdat ik dat niet wilde beperken tot alleen tekstbestanden, besloot ik om alle invoer eerst om te zetten naar BASE64 zodat ik dan dus een goed afgebakende tekenset had om mn tabula recta mee te maken. Alle uitvoer gaat eerst naar een tekstbox (met daarbij de mogelijkheid om het op te slaan als bestand). Maar ik ga nu verdedigen dat ik de invoer beperk tot tekst-only als gevolg van de wijze waarop het Vigenère cipher is opgebouwd, behalve als ik een andere zwaarwegende reden vind om alsnog die BASE64 encoding te behouden.

[MSalters]

Nee, sorry, ik ben het niet eens met je aannames over sleutellengte. Ja, ik weet dat je in een aanval op de simpele, ongemodificeerde Vigenère codering (over een alfabet met 26 symbolen) de sleutellengte graag wil hebben. Kwestie van een autocorrelatie bepalen. Maar in dit geval is je sleutel de uitkomst van een SHA256 hash, dus lengte 64, een alfabet met 256 symbolen (bytes), en een uniforme kansverdeling. Gezien het grote aantal sleutels wat nog steeds mogelijk is, hoef je je geen zorgen te maken.
Jouw probleem is dat ik de effectieve sleutellengte bepaal (autocorrelatie), daaruit de mogelijke wachtwoord lengte(s), en die vervolgens brute-force. Het aantal mogelijke wachtwoorden is namelijk veel kleiner als het aantal mogelijke uitkomsten van de (unsalted) SHA256 hash.

Wat betreft je output, een klein nadeelje van de Vigenère sleutels is inderdaad dat je output alfabet net zo groot moet zijn als je input alfabet. Base64 werkt als een alfabet reductie (256->64 symbolen) waardoor je ASCII als input en output alfabet kunt gebruiken. Maar die BASE64 conversie kun je ook na encryptie doen.

[ Voor 18% gewijzigd door MSalters op 29-04-2009 13:48 ]

[wizzkizz]

MSalters schreef op woensdag 29 april 2009 @ 13:41:
Nee, sorry, ik ben het niet eens met je aannames over sleutellengte. Ja, ik weet dat je in een aanval op de simpele, ongemodificeerde Vigenère codering (over een alfabet met 26 symbolen) de sleutellengte graag wil hebben. Kwestie van een autocorrelatie bepalen. Maar in dit geval is je sleutel de uitkomst van een SHA256 hash, dus lengte 64, een alfabet met 256 symbolen (bytes), en een uniforme kansverdeling. Gezien het grote aantal sleutels wat nog steeds mogelijk is, hoef je je geen zorgen te maken.
Jouw probleem is dat ik de effectieve sleutellengte bepaal (autocorrelatie), daaruit de mogelijke wachtwoord lengte(s), en die vervolgens brute-force. Het aantal mogelijke wachtwoorden is namelijk veel kleiner als het aantal mogelijke uitkomsten van de (unsalted) SHA256 hash.

Hmm, als ik nog eens goed over jouw uitleg nadenk, klinkt het logisch. In mijn aanname over de sleutellengte zag ik over het hoofd dat je bij het gebruik van 256 symbolen inderdaad een uniforme kansverdeling hebt.
Dus als ik de input comprimeer en een salted SHA256/SHA512 hash gebruik als sleutel, is het (voor zover dit oude algoritme het toelaat) in enige mate bestand tegen cryptoanalyse.
Dan zorg ik verder wel voor een waarschuwing als het ingevoerde wachtwoord zwak is en is het aan de gebruiker (hm, wellicht alleen ikzelf ) om daar wat mee te doen

[MSalters]

Eerlijk gezegd: je komt al vrij dicht bij het punt waarop de meest zinnige aanval een brute-force dictionary attack is. De known-text delen van de zip header zijn kleiner dan je sleutellengte, en de variable lengte van symbolen in je zip alfabet zijn iha ongelijk aan de vaste lengte (8 bits) in je encoding alfabet.