XTEA Verschlüsselung - Verbessern, Optimieren



  • Hallo,

    ich habe versucht den hier in C++ umzusetzten: https://en.wikipedia.org/wiki/XTEA

    Mit umsetzen meine ich, dass man Dateien damit ver-/entschlüsseln kann. Mir ist klar, dass ich viele Dinge außen vor lasse, z.B. arbeite ich mit dem ECB block mode of operation.

    There are major security issues in using ECB mode (duplicate plaintext blocks give the same ciphertext block) and its use is generally discouraged.

    Außerdem fehlen bei mir irgendwelche message authentication codes (MAC) etc. Ich wollte jetzt erstmal klein anfangen und andere Sachen später hinzufügen.

    Ich weiß auch, dass man allg. nicht sein eigenes Crypto Zeug machen soll (genau aus den oben genannten Gründen: Man kann sehr viel falsch machen). Aber ich mache das nur zu Lernzwecken und immerhin hab ich mir nicht den Algorithmus selbst ausgedacht.

    Hier der Code (header only).

    // xtea.hpp
    #pragma once
    
    #undef max
    
    #include <array>
    #include <cassert>
    #include <cstdint>
    #include <fstream>
    #include <stdexcept>
    #include <vector>
    
    namespace xtea {
    namespace {
    	// https://de.wikipedia.org/wiki/Extended_Tiny_Encryption_Algorithm
    
    	using Key = std::array<uint32_t, 4>; // 128bit key
    
    	class Block {
                 // soll einen 64bit Block für die Verschlüsselung darstellen
    	public:
    		void encipher(const Key& key, unsigned numCycles = defCycleCount);
    		void decipher(const Key& key, unsigned numCycles = defCycleCount);
    
    		std::istream& read(std::istream& is);
    		std::ostream& write(std::ostream& os) const;
    
    		void pad(std::size_t numOccupiedBytes);  // PKCS #5/#7 Padding
    		void set_padded(bool b) { isPadded = b; }  
    
    	private:
    		static constexpr unsigned defCycleCount{ 32 };
    		static constexpr std::size_t bytesPerBlock{ 8 };
    		static constexpr uint32_t delta{ 0x9E3779B9 };
    
    		std::array<uint32_t, 2> data;  // 64bit block cipher
    		bool isPadded{};
    	};
    
    	void Block::pad(std::size_t bytesUsed)
    	{    // Eigenkreation, soll padding implementieren: https://en.wikipedia.org/wiki/Padding_(cryptography)#PKCS7
    		auto padCount = Block::bytesPerBlock - bytesUsed;
    		assert(padCount < 256);
    		auto bytes = reinterpret_cast<uint8_t*>(data.data());
    		for (std::size_t i = bytesUsed; i < bytesPerBlock; ++i)
    			bytes[i] = static_cast<uint8_t>(padCount);
    		isPadded = true;
    	}
    
            // Die beiden Funktionen habe ich von Wikipedia geklaut und etwas abgeändert, wie es für mich besser erschien
    
    	void Block::encipher(const Key& key, unsigned numCycles) {
    		auto& v0 = data[0];
    		auto& v1 = data[1];
    		uint32_t sum{};
        	while (numCycles--) {
            	v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
            	sum += delta;
            	v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
        	}
    	}
    
    	void Block::decipher(const Key& key, unsigned numCycles) {
    		auto& v0 = data[0];
    		auto& v1 = data[1];
    		uint32_t sum{ delta * numCycles };
        	while (numCycles--) {
            	v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum>>11) & 3]);
            	sum -= delta;
           		v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
        	}
    	}
    
            // Die nächsten beiden Funktionen sollen nur den hässlichen cast verstecken
    	std::istream& Block::read(std::istream& is)
    	{
    		return is.read(reinterpret_cast<char*>(data.data()), bytesPerBlock);
    	}
    
    	std::ostream& Block::write(std::ostream& os) const
    	{
    		auto size = bytesPerBlock;
    		if (isPadded) // PKCS #7 Padding, hier werden die Padding bytes sozusagen "abgeschnitten"
    			size -= reinterpret_cast<const uint8_t*>(data.data())[bytesPerBlock - 1];
    		return os.write(reinterpret_cast<const char*>(data.data()), size);
    	}
    
    	void write_blocks(const std::vector<Block>& blocks, const std::string& filePath)
    	{
    		std::ofstream file{ filePath, std::ios::binary };
    		if (!file)
    			throw std::runtime_error{ "xtea::write_blocks - Unable to open file " + filePath };
    
    		for (const auto& block : blocks)
    			block.write(file);
    		if (!file)
    			throw std::runtime_error{ "xtea::write_blocks - Failed writing blocks to " + filePath };
    	}
    
    	void encrypt_file(const std::string& path, const Key& key)
    	{
    		std::ifstream file{ path, std::ios::binary };
    		if (!file) 
                throw std::runtime_error{ "xtea::encrypt_file - Unable to open file " + path };
    
            std::vector<Block> blocks(1);
    		for (Block b; blocks.back().read(file); ) {
    			blocks.back().encipher(key);
    			blocks.emplace_back();
    		}
    		blocks.back().pad(file.gcount());
    		blocks.back().encipher(key);
    		file.close();
    		write_blocks(blocks, path);
    	}
    
    	void decrypt_file(const std::string& path, const Key& key)
    	{
    		std::vector<Block> blocks;
    		std::ifstream file{ path, std::ios::binary };
    		if (!file) throw std::runtime_error{ "xtea::decrypt_file - Unable to open file " + path };
    		for (Block b; b.read(file); ) {
    			b.decipher(key);
    			blocks.emplace_back(b);
    		}
    		blocks.back().set_padded(true);
    		file.close();
    		write_blocks(blocks, path);
    	}
    
    } /* namespace */
    } /* namespace xtea */
    

    Falls jemand Lust/Zeit hat schnell drüberzuschauen, meine Punkte wären:

    - Optimieren von encipher/decipher , auf Wikipedia heißt es z.B.

    To additionally improve speed, the loop can be unrolled by pre-computing the values of sum+key[].

    Aber ich verstehe nicht so wirklich was gemeint ist mit diesem loop unrolling. Natürlich bleibt auch das Multithreading, aber ich glaube das ist nicht notwendig bzw. zu kompliziert.

    - Optimieren von read/write, da gehen ca 12% - 15% drauf und ich denke entweder mache ich was falsch, oder ich sollte C files oder mmap files oder sowas verwenden.

    - Ob mein Aufbau an sich gut ist, z.B. die Block Klasse gut oder eher Blödsinn

    - Es sind viele casts drin und ich habe bisher nie reinterpret_cast verwendet, aber es kommt mir nicht sehr schön vor.

    - Hab ich sonstige offensichtliche Fehler drin (v.a. sprachliche Fehler in C++)

    Was die technische Seite der Kryptografie angeht bin ich mir bewusst, dass in der Form das Ganze nicht sehr gut ist, habe ich zu Beginn ja schon erwähnt.

    Vielen Dank im Voraus

    LG



  • Also ich würde empfehlen dich erstmal auf Fehler zu konzentrieren bevor du anfängst etwas zu optimieren.

    Hab nur kurz drügergelesen, dabei sind mir folgende Dinge aufgelallen:

    * Bei ECB musst du den letzten Block im verschlüsselten File ganz rausschreiben, du kannst nicht einfach die letzten paar Byte weglassen - auch wenn diese im Plaintext Padding waren. Deine write Funktion lässt aber immer die letzten paar Byte weg. Damit es funktioniert wie es soll müsstest du im verschlüsselten File alle Blocks vollständig speichern und dir noch die Info dazuspeichern wie viele Padding-Bytes der letzte Block enthält. Was auch einer der Nachteile des ECB Mode ist.

    * Der Code in deiner encrypt_file Funktion behandelt das File-Ende nicht korrekt, wenn die Filegrösse ohne Rest durch die Blockgrösse dividierbar ist. Dann merkt dein Code nämlich erst nach dem Lesen des letzten Blocks dass kein vollständiger Block mehr gelesen werden konnte, aber gcount ist dann 0, d.h. du codierst einen leeren Block. Der oben beschriebene Fehler maskiert das dann allerdings wieder, da der Block auf 100% Padding gesetzt wird, und deine write Funktion ja kein Padding speichert, für den "gepaddeten" Block also auch kein einziges Byte schreibt.

    BTW: Ich kann mir nicht vorstellen dass du den Code getestet hast. Sonst hätte dir ja auffallen müssen dass er nicht korrekt funktioniert. Also: testen, testen, testen. Möglichst mit Tests die sämtliche Sonderfälle abdecken. Also auf jeden Fall mit eine File welches Padding erfordert und mit einem welches kein Padding erfordert.

    - Ob mein Aufbau an sich gut ist, z.B. die Block Klasse gut oder eher Blödsinn

    Zumindest unüblich weil von der Performance her schlecht.
    Und zwar stört dabei hauptsächlich der zusätzliche bool. Der führt dazu dass du unnötig viel Speicher verbrauchst, und bei üblichen Compilern auch dazu dass die grösse der Klasse keine power-of-two mehr ist (sondern 12 Byte).
    Auch vom Software-Design her ist es fraglich ob die "is padded" Information in jedem Block enthalten sein sollte. Weil schliesslich immer nur der letzte Block padded sein darf. Kann man aber sicher unterschiedlicher Meinung sein diesbezüglich.

    Gibt dann noch weiter Dinge die man zum Thema "schön" und zum Thema Performance sagen könnte, aber wie gesagt: kümmer dich erstmal darum dass die Sache korrekt funktioniert.

    ps:
    reinterpret_cast<const uint8_t*> ist streng genommen falsch, da nicht garantiert ist dass uint8_t immer unsigned char (oder char ) ist. Was an der Stelle wichtig ist, da nur für char und unsigned char die Aliasing-Ausnahmen gelten, auf die du dich hier verlässt. => Verwende unsigned char .



  • Hallo hustbear,

    vielen Dank für Deine umfangreiche und hilfreiche Antwort.

    hustbaer schrieb:

    * Der Code in deiner encrypt_file Funktion behandelt das File-Ende nicht korrekt, wenn die Filegrösse ohne Rest durch die Blockgrösse dividierbar ist. Dann merkt dein Code nämlich erst nach dem Lesen des letzten Blocks dass kein vollständiger Block mehr gelesen werden konnte, aber gcount ist dann 0, d.h. du codierst einen leeren Block.

    Wenn ich Dich richtig verstehe meinst du damit, dass bei fileSize % blockSize == 0 ein ganzer Block padding bytes angefügt wird, also ca. so:

    .... | 08 08 08 08 08 08 08 08 |
    

    Wenn ich dieses padding Verfahren richtig verstanden habe, dann ist das so gewollt:

    [...] The padding string PS will satisfy one of the following statements:

    PS = 01, if ||M|| mod 8 = 7 ;
    PS = 02 02, if ||M|| mod 8 = 6 ;
    ...
    PS = 08 08 08 08 08 08 08 08, if ||M|| mod 8 = 0.
    https://tools.ietf.org/html/rfc2898

    In anderen Worten, selbst bei einer leeren Datei werden die 8 padding bytes mitverschlüsselt. So habe ich das zuminest interpretiert.

    Hier meine korrigierte Version

    using Key = std::array<uint32_t, 4>; // 128bit key
    using Block = std::array<uint32_t, 2>; // 64bit blocks
    
    static constexpr std::size_t blockSize{ 8 };
    static constexpr uint32_t delta{ 0x9E3779B9 };
    static constexpr unsigned defaultCycles{ 32 };
    static const Key defaultKey{ 1, 2, 3, 4 };
    
    void encipher(Block& data, const Key& key, unsigned cycles = defaultCycles) {
        auto& v0 = data[0];
        auto& v1 = data[1];
        uint32_t sum{};
        while (cycles--) {
            v0 += (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
            sum += delta;
            v1 += (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum >> 11) & 3]);
        }
    }
    
    void decipher(Block& data, const Key& key, unsigned cycles = defaultCycles) {
        auto& v0 = data[0];
        auto& v1 = data[1];
        uint32_t sum{ delta * cycles };
        while (cycles--) {
            v1 -= (((v0 << 4) ^ (v0 >> 5)) + v0) ^ (sum + key[(sum >> 11) & 3]);
            sum -= delta;
            v0 -= (((v1 << 4) ^ (v1 >> 5)) + v1) ^ (sum + key[sum & 3]);
        }
    }
    
    std::ostream& write_block(std::ostream& os, const Block& block)
    {
        return os.write(reinterpret_cast<const char*>(block.data()), blockSize);
    }
    
    std::ostream& write_padded_block(std::ostream& os, const Block& block)
    {
        auto bytes = reinterpret_cast<const unsigned char*>(block.data());
        auto padCount = bytes[blockSize - 1];
        return os.write(reinterpret_cast<const char*>(block.data()), blockSize - padCount);
    }
    
    std::istream& read_block(std::istream& is, Block& block)
    {
        return is.read(reinterpret_cast<char*>(block.data()), blockSize);
    }
    
    void pad_block(Block& block, unsigned numPadded)
    {
        assert(numPadded < 256);
        auto bytes = reinterpret_cast<unsigned char*>(block.data());
        for (auto i = blockSize - numPadded; i < blockSize; ++i)
            bytes[i] = static_cast<unsigned char>(numPadded);
    }
    
    void write_encrypted_blocks(const std::string& path, const std::vector<Block>& blocks)
    {
        std::ofstream out{ path, std::ios::binary };
        for (const auto& b : blocks)
            write_block(out, b);
        if (!out) throw std::runtime_error{ "Unable to write file: " + path };
    }
    
    void write_decrypted_blocks(const std::string& path, const std::vector<Block>& blocks)
    {
        std::ofstream out{ path, std::ios::binary };
        for (std::size_t i = 0; i < blocks.size() - 1; ++i)
            write_block(out, blocks[i]);
        write_padded_block(out, blocks.back());
        if (!out) throw std::runtime_error{ "Unable to write file: " + path };
    }
    
    std::vector<Block> read_and_encrypt_blocks(std::istream& is, const Key& key)
    {
        std::vector<Block> blocks(1);
        while (read_block(is, blocks.back())) {
            encipher(blocks.back(), key);
            blocks.emplace_back();
        }
        pad_block(blocks.back(), static_cast<unsigned>(blockSize - is.gcount()));
        encipher(blocks.back(), key);
        return blocks;
    }
    
    std::vector<Block> read_and_decrypt_blocks(std::istream& is, const Key& key)
    {
        std::vector<Block> blocks;
        for (Block block; read_block(is, block); ) {
            decipher(block, key);
            blocks.emplace_back(block);
        }
        return blocks;
    }
    
    void encrypt_file(const std::string& path, const Key& key)
    {
        std::ifstream file{ path, std::ios::binary };
        if (!file) throw std::runtime_error{ "Unable to open file: " + path };
        auto blocks = read_and_encrypt_blocks(file, key);
        file.close();
        write_encrypted_blocks(path, blocks);
    }
    
    void decrypt_file(const std::string& path, const Key& key)
    {
        std::ifstream file{ path, std::ios::binary };
        if (!file) throw std::runtime_error{ "Unable to open file: " + path };
        auto blocks = read_and_decrypt_blocks(file, key);
        file.close();
        write_decrypted_blocks(path, blocks);
    }
    

Log in to reply