Extra bytes in encryption block

[vdvleon]

Hallo, ik ben voor mijn profielwerkstuk zelf een encryptie aan het ontwerpen. Ik doe het iets moeilijker dan ik zou hoeven maar maak hem in C++. De encryptie zelf is eigenlijk wel af. Hij werkt in blokken van een bepaalde aantal bytes. Maar omdat de input die je wilt encrypten niet altijd uit precies een n aantal blokken van dat aantal bytes bestaat heb je het laatste blok bijna nooit precies vol. Wat is nou de beste manier om dit blok te vullen en dit zo te doen dat je tijdens de decryption deze extra bytes weer eraf kunt halen?

[Krypt]

Heb helemaal geen ervaring ermee, maar ik zou het 1e block gebruiken als header met oa info over de lengte.
Het laatste block opvullen met 0'en en de boel encrypten. Bij decrypten de lengte uit block 1 halen en alles opslaan tot die lengte.

[Soultaker]

Er zijn verschillende methoden voor; ze komen er allemaal op neer dat je je data aanvult met padding bytes tot een block boundary op zo'n manier dat je de padding weer ongedaan kan maken. In sommige gevallen betekent dat dat je data die wél op een block boundary eindigt ook moet padden (dat is in het algemeen onvermijdelijk).

Headers van te voren toevoegen (zoals Krypt suggereert) is niet zo gebruikelijk, omdat je dan niet handig de gecodeerde tekst kunt streamen als de uiteindelijke grootte niet van te voren bekend is. Je kunt die header wel weer aan het einde toevoegen maar dan moet je een soort containerformaat erbij verzinnen; dat is waarschijnlijk complexer dan gewoon padden, waar het in de praktijk dus meestal op neer komt.

Overigens is voor veel encryptiemethoden de manier van padding niet gedefinieerd, je hoeft het zeker niet als onderdeel van je encryptie-algoritme te specificeren, al is 't wel handig om mee te testen natuurlijk.

Als je nog inspiratie zoekt, staat er wel een lijstje met veelvoorkomende methoden op Wikipedia:
• Padding methods

[vdvleon]

Ik zou op 1 of ander manier de overige bytes kunnen aanvullen met random chars (zodat je moeilijker door plain text searching (ofsow iets) de key of de rest van het blok kunt achterhalen) en dan de extra bytes die zijn toegevoegd nog weer extra los in een extra laatste byte mee sturen? Of is dit niet veilig genoeg?

[EDIT]
Dat is inderdaad ook waar, ik hoef mijn padding systeem etc. ook niet aan encryptie toe te voegen nee. Dat heb ik ook niet gedaan.

Het ziet er nu zo uit:

C++:

bool encrypt(std::iostream &input, std::iostream &output, int &extra_bytes);
bool decrypt(std::iostream &input, std::iostream &output, int extra_bytes);

Dus na het encrypten bevat de variable extra_bytes de aantal extra bytes die zijn toegevoegd, en daar kan je mee doen wat je wilt. Als je dan weer gaat decrypten moet je deze extra bytes op geven. Doe je dit niet, kan het zijn dat het bestand achteraan wat random rommel er bij heeft staan.

[ Voor 50% gewijzigd door vdvleon op 03-01-2009 21:20 ]

[matthijsln]

Het ziet er nu zo uit:

C++:

bool encrypt(std::iostream &input, std::iostream &output, int &extra_bytes);
bool decrypt(std::iostream &input, std::iostream &output, int extra_bytes);

Dus na het encrypten bevat de variable extra_bytes de aantal extra bytes die zijn toegevoegd, en daar kan je mee doen wat je wilt. Als je dan weer gaat decrypten moet je deze extra bytes op geven. Doe je dit niet, kan het zijn dat het bestand achteraan wat random rommel er bij heeft staan.

Dat is natuurlijk een onnodige restricie. Zet gewoon (zoals op de wikipedia pagina staat uitgelegd) in je laatste byte hoeveel bytes je hebt gepad, en haal die er bij het decrypten vanaf. De API hoeft dan helemaal niks van padding of extra bytes te weten.

[vdvleon]

Dat heb ik gedaan. Na het laatste blok word gewoon nog een extra Byte toegevoegd met de padding lengte.

Mijn encryptie doet er nu ongeveer 12s over om te encrypten en 13s over om te decrypten en dit bij een bestand van 7230464 Bytes (ongeveer 7MB). Is dit te langzaam? Of is dit snel genoeg? Wat vinden jullie?

Ik heb voor deze test niet uiterst precieze meting gedaan (reken anders maar - 2s). Mijn encryptie werkt dus met std::iostream's. Zo kun je een fstream als input en output geven. Op die manier kan hij dus in/uit bestanden lezen en schrijven. Je kan ook als input stream bijvoorbeeld std::cin op geven. Op die manier word bijv. alles wat je typed ge-encrypt en weg geschreven. Volgens mij is met deze streams werken wel het snelst, dus daar zou het probleem (als die er is) wel niet liggen.

[Soultaker]

Tja, wat is snel. AES doet daar hooguit een paar honderd milliseconden over. Maar dan heb je het wel over een state-of-the-art algoritme en een zeer gestroomlijnde implementatie. Ik denk niet dat je daar als scholier mee vergeleken zal worden. (Met andere woorden: als het principe goed werkt, doet de snelheid er waarschijnlijk niet zoveel toe.)

Btw, weet je zeker dat je geen std::istream en std::ostream als parameters wil geven? Niet alle stream objecten kunnen zowel lezen als schrijven namelijk.

[Gomez12]

Tsja, qua snelheid zou ik gewoon even aan wat studiegenoten vragen wat die voor snelheden halen.

Ik vind het namelijk niet erg snel, en aangezien je meer doet dan de opdracht vraagt heb je altijd het risico dat je meerwerk het ontzettend vertraagt.

[vdvleon]

Ik heb ook een 1GB test gedaan. Hier deed hij d8t ik ongeveer 20 min over (encrypten of decrypten). Dus dat is onverveer 0.8 MB/s. Het kan ook zijn dat mijn hardware het probleem is. Want die hardeschijf word hier thuis best zwaar gebruikt, dus zou best kunnen dat het lees en schrijven een probleem is of dat de block grote iets raars is waardoor het wegschrijven en lezen niet helemaal optimaal gaat.

Over de istream en ostream: mogelijk probleem opgelost.

C++:

void encrypt_block(jews_block &block){
    // vars
    int ri, i;
    jews_block block2;
    
    // init key
    init_key();
    
    // XOR
    for(i=0; i<26; i++){
        block.block[i] ^= current_key.key[i];
    }
    
    // each 17 rounds
    for(ri=0; ri<17; ri++){
        // box
        block2 = block;
        for(i=0; i<26; i++){
            block.block[i] = block2.block[jews_box[i]];
        }
            
        // subbytes & XOR
        for(i=0; i<26; i++){
            block.block[i] = jews_subbytes[block.block[i]];
            block.block[i] ^= current_key.key[i];
        }
        
        // rotate key
        if(ri==2) rotate_key(ukr_a);
        else if(ri==7) rotate_key(ukr_b);
        else if(ri==13) rotate_key(ukr_c);
        else if(ri==15) rotate_key(ukr_d);
        else rotate_key(1);
    }
}

Dit is nu mijn encryption functie voor elke block. Zou ik hier nog veel snelheid winst kunnen maken?

C++:

void rotate_key(int steps){
    // left or right?
    if(steps<0) rotate_key_left(-steps);
    else rotate_key_right(steps);
}
void rotate_key_right(int steps){
    // vars
    unsigned char last;
    int i, j;
    
    // check
    if(steps<0){
        rotate_key_left(-steps);
        return;
    }
    steps = steps%64;
    
    // rotate
    for(j=0; j<steps; j++){
        // shift key
        last = current_key.key[63];
        for(i=63; i>0; i--){
            current_key.key[i] = current_key.key[i-1];
        }
        current_key.key[0] = last;
    }
}
// .. rotate_key_left is zelfde als right, maar dan de andere kant op (duh)

Of is de rotate functie het probleem? Heeft iemand een manier om dit te kunnen meten? Ik heb het zelf geprobeert met clock() maar deed is niet goed gelukt. Of ik begrijp die functie niet. Maar bij mij gaf hij maar om de x aantal keer een waarde terug... Zijn er programma die code kunnen uitvoeren met een overzicht van hoelang elke functie duurt? (voor unix / linux)

[vdvleon]

Ik heb de rotate functie wat verbeterd:

C++:

void rotate_key_right(int steps){
    // vars
    jews_key tmp;
    int i;
    
    // check
    if(steps==0) return;
    if(steps<0){
        rotate_key_left(-steps);
        return;
    }
    steps = steps%64;
    
    // rotate
    for(i=0; i<steps; i++) tmp.key[i] = current_key.key[63-steps+i];
    for(i=63; i>steps-1; i--) current_key.key[i] = current_key.key[i-1];
    for(i=0; i<steps; i++) current_key.key[i] = tmp.key[i];
}

Het scheelt soms heel wat miliseconden op de vorige versie.

[EDIT]
Ik kom nu tot de 0.97 MB/s

[ Voor 3% gewijzigd door vdvleon op 04-01-2009 21:23 ]

[Gerco]

vdvleon schreef op zondag 04 januari 2009 @ 20:15:
Zijn er programma die code kunnen uitvoeren met een overzicht van hoelang elke functie duurt? (voor unix / linux)

http://valgrind.org/ (Callgrind)

Kun je ook gelijk op memory leaks checken

[vdvleon]

Ok, dankje wel. Ik word er alleen niet echt wijs uit... Ik probeer het nog wel een uit te zoeken. ik ga nu eerst een pitten.

[vdvleon]

Ik heb heel wat fouten in mijn encryptie opgelost:

C++:

int mod(int b, int m){
    // check for negative values
    if(b<0){
        b = m-((-b)%m);
        return b==m?0:b;
    }
    
    // return mod action
    return b%m;
}

void init_key_e(){
    // (re)set current_key_e
    current_key_e = key_e;
}

void init_key_d(){
    // (re)set current_key_d
    current_key_d = key_d;
}

int get_round_rotate(int round){
    // 4 special rounds, rest just 1 rotate
    switch(round){
        case 2:     return ukr_a;
        case 7:     return ukr_b;
        case 13:    return ukr_c;
        case 15:    return ukr_d;
    }
    return 1;
}

void encrypt_block(block &block){
    // vars
    int ri, i;
    block block2;
    
    // init key
    init_key_e();
    
    // XOR
    for(i=0; i<26; i++) block.block[i] ^= current_key_e.key[i];
    
    // each 17 rounds
    for(ri=0; ri<17; ri++){
        // box & subbytes & XOR
        block2 = block;
        for(i=0; i<26; i++)
            block.block[box_reverse[i]] = subbytes[block2.block[box[i]]]^current_key_e.key[i];
        
        // rotate key
        rotate_key_e(get_round_rotate(ri));
    }
}

void decrypt_block(block &block){
    // vars
    int ri, i;
    block block2;
    
    // init key
    init_key_d();
    
    // each 17 rounds
    for(ri=16; ri>=0; ri--){
        // rotate key
        rotate_key_d(get_round_rotate(ri));
        
        // box & XOR & subbytes
        block2 = block;
        for(i=0; i<26; i++)
            block.block[box[i]] = subbytes_reverse[block2.block[box_reverse[i]]^current_key_d.key[i]];
    }
    
    // XOR
    for(i=0; i<26; i++) block.block[i] ^= current_key_d.key[i];
}

void rotate_key_e(int steps){
    // rotate key (+: >>, -: <<)
    rotate_key(current_key_e, steps);
}

void rotate_key_d(int steps){
    // rotate key (+: <<, -: >>)
    rotate_key(current_key_d, -steps);
}

void rotate_key(key &key, int steps){
    // vars
    key tmp;
    int i;
    
    // check
    if(steps==0) return;
    steps = mod(steps, 64);
    
    // rotate
    for(i=0; i<steps; i++) tmp.key[i] = key.key[64-steps+i];
    for(i=63; i>steps-1; i--) key.key[i] = key.key[i-steps];
    for(i=0; i<steps; i++) key.key[i] = tmp.key[i];
}

De mod functie zorgd ervoor dat je bij rotate_key bij een positieve steps naar rechts rotate en bij een negatieve naar links.
De vars ukr_a, ukr_b, ukr_c en ukr_d (unique key rotation) worden aan de hand van de key berekend.

[Soultaker]

Is je key nu een array van "bits"? Geen wonder dat roteren dan niet opschiet.

[MSalters]

Sterker nog, het is vermoedelijk veel sneller als je de key niet in memory roteert. Het is C++, dus maak een class Key met een custom operator[]. Daarin roteer je de array index over (-steps), in plaats van de array zelf over +steps.

[vdvleon]

Nee, hij bestaat niet uit bits. Waar bazeer je dat op?

Ik zou eens kijken of ik inderdaad de key niet kan aanpassen (het rotate gebeuren). En in dit geval is key geen class maar een struct, maar dat maakt in dit geval geen verschil

Nu zijn de block functies:

C++:

void encrypt_block(block &block){
    // vars
    int ri, i;
    block block2;
    
    // init key
    init_key_e();
    
    // XOR
    for(i=0; i<26; i++) block[i] ^= current_key_e[i];
    
    // each 17 rounds
    for(ri=0; ri<17; ri++){
        // box & subbytes & XOR
        block2 = block;
        for(i=0; i<26; i++)
            block[box_reverse[i]] = subbytes[block2[box[i]]]^current_key_e[i];
        
        // rotate key
        current_key_e.rotate(get_round_rotate(ri));
    }
}

void decrypt_block(block &block){
    // vars
    int ri, i;
    block block2;
    
    // init key
    init_key_d();
    
    // each 17 rounds
    for(ri=16; ri>=0; ri--){
        // rotate key
        current_key_d.rotate(-get_round_rotate(ri));
        
        // box & XOR & subbytes
        block2 = block;
        for(i=0; i<26; i++)
            block[box[i]] = subbytes_reverse[block2[box_reverse[i]]^current_key_d[i]];
    }
    
    // XOR
    for(i=0; i<26; i++) block[i] ^= current_key_d[i];
}

De key struct ziet er zo uit:

C++:

struct key{
    bool isset;
    int _rotate;
    unsigned char key[64];
    
    key() : isset(false), _rotate(0) {}
    
    void set(std::string str){
        if(str.length()==64){
            for(int i=0; i<64; i++) key[i] = (unsigned char)str[i];
            isset = true;
        }
    }
    
    std::string get(){
        std::string str;
        if(isset){
            for(int i=0; i<64; i++) str += (char)key[i];
        }
        return str;
    }
    
    void rotate(int steps){
        _rotate = mod(_rotate-steps, 64);
    }
    
    key &operator=(key _key){
        if(_key.isset){
            for(int i=0; i<64; i++) key[i] = _key.key[i];
            isset = true;
        }
        return *this;
    }
    
    unsigned char operator[](int pos){
        return key[mod(pos+_rotate, 64)];
    }
};

[ Voor 77% gewijzigd door vdvleon op 06-01-2009 21:43 ]

[Soultaker]

vdvleon schreef op dinsdag 06 januari 2009 @ 16:17:
Nee, hij bestaat niet uit bits. Waar bazeer je dat op?

Ik zou zo'n key in een 64-bits integer stoppen, dan kun je 'm roteren met twee shifts en een or-operatie (of met een enkele instructie, maar daar kun je vanuit C++ niet op een standaardmanier bij). Je code suggereert dat de key nu wel bit-voor-bit geroteerd wordt en dat is natuurlijk nogal traag.

[vdvleon]

Soultaker schreef op dinsdag 06 januari 2009 @ 16:35:
[...]

Ik zou zo'n key in een 64-bits integer stoppen, dan kun je 'm roteren met twee shifts en een or-operatie (of met een enkele instructie, maar daar kun je vanuit C++ niet op een standaardmanier bij). Je code suggereert dat de key nu wel bit-voor-bit geroteerd wordt en dat is natuurlijk nogal traag.

C++:

//...
unsigned char key[64]; 
// ...
void rotate(int steps){
    _rotate = mod(_rotate-steps, 64);
}
// ...
unsigned char operator[](int pos){
      return key[mod(pos+_rotate, 64)];
} 

Het gaat hier niet om een 'bit array' of iets in die trant. Het is een array van 64 bytes. Dus kan ik hem ook niet in een 64 bit integer stoppen (kan ook niet op een 32 bit systeem...). Dus ik denk dit op het moment de snelste manier van rotate is.

[Verwijderd]

Dit zou in principe hetzelfde moeten doen als de huidige rotate_key.

C++:

void rotate_key(key &key, int steps){    
    // check
    if(steps==0) return;
    int size = mod(steps, 64); //Array size
    steps = size/2;            //Delen door 2, is size oneven afronden naar beneden
    
    // rotate
    for(int i=0; i<steps; i++)
    {
        unsigned char Temp;
        Temp            = key.key[i];
        key.key[i]      = key.key[size-i];
        key.key[size-i] = Temp;
    }
}

Misschien is het ook beter om van deze een functie te maken in de key klasse, dan kan de compiler zich meer beperken van waar het allemaal toegepast moet kunnen worden en kan andere optimalisaties uitvoeren.
Maar goed, 10 minuten voor encrypten of decrypten van 1 gb is aardig lang. Maar dat kan talloze redenen hebben, misschien lees/schrijf je te kleine blokken in je files, draai je het sowieso al in Release mode en dergelijke.

Als laatst, kijk uit voor series van nullen. Als je die xor'ed, krijg je dat de wachtwoord er staat. Niet dat meteen 1 zal denken, hey dat zal de wachtwoord wel zijn. Maarja het is niet echt zon veilig idee

[vdvleon]

Verwijderd schreef op woensdag 07 januari 2009 @ 12:05:
Dit zou in principe hetzelfde moeten doen als de huidige rotate_key.

C++:

void rotate_key(key &key, int steps){    
    // check
    if(steps==0) return;
    int size = mod(steps, 64); //Array size
    steps = size/2;            //Delen door 2, is size oneven afronden naar beneden
    
    // rotate
    for(int i=0; i<steps; i++)
    {
        unsigned char Temp;
        Temp            = key.key[i];
        key.key[i]      = key.key[size-i];
        key.key[size-i] = Temp;
    }
}

Misschien is het ook beter om van deze een functie te maken in de key klasse, dan kan de compiler zich meer beperken van waar het allemaal toegepast moet kunnen worden en kan andere optimalisaties uitvoeren.
Maar goed, 10 minuten voor encrypten of decrypten van 1 gb is aardig lang. Maar dat kan talloze redenen hebben, misschien lees/schrijf je te kleine blokken in je files, draai je het sowieso al in Release mode en dergelijke.

Als laatst, kijk uit voor series van nullen. Als je die xor'ed, krijg je dat de wachtwoord er staat. Niet dat meteen 1 zal denken, hey dat zal de wachtwoord wel zijn. Maarja het is niet echt zon veilig idee

C++:

struct key{ 
    bool isset; 
    int _rotate; 
    unsigned char key[64]; 
     
    key() : isset(false), _rotate(0) {} 
     
    void set(std::string str){ 
        if(str.length()==64){ 
            for(int i=0; i<64; i++) key[i] = (unsigned char)str[i]; 
            isset = true; 
        } 
    } 
     
    std::string get(){ 
        std::string str; 
        if(isset){ 
            for(int i=0; i<64; i++) str += (char)key[i]; 
        } 
        return str; 
    } 
     
    void rotate(int steps){ 
        _rotate = mod(_rotate-steps, 64); 
    } 
     
    key &operator=(key _key){ 
        if(_key.isset){ 
            for(int i=0; i<64; i++) key[i] = _key.key[i]; 
            isset = true; 
        } 
        return *this; 
    } 
     
    unsigned char operator[](int pos){ 
        return key[mod(pos+_rotate, 64)]; 
    } 
};

Zoals je hier kunt zien heb ik al een andere rotate manier (in de key struct zelf).
Wat bedoel je met Release Mode?

Als oplossing voor de snelheid zou ik de aantal rondes omlaag kunnen gooien (er zijn er nu 17). Alleen weet ik niet hoe je kan bepalen vanaf welke aantal rondes het veilig is.

Die 0 als key is inderdaad een probleem bij een XOR bewerking. Maar zoals je kan zien (of in iedergeval als je de hele code kan zien:P) word elke byte ook vervangen voor een andere byte uit een tabel.

C++:

unsigned char box[256] = { 3, 232, 43 ..... 34, 1, 67};