XTEA Encryption Algorithm and basic block chaining

Share your advanced PureBasic knowledge/code with the community.
Post Reply
User avatar
pdwyer
Addict
Addict
Posts: 2813
Joined: Tue May 08, 2007 1:27 pm
Location: Chiba, Japan

XTEA Encryption Algorithm and basic block chaining

Post by pdwyer »

This is a little cmdline tool I wrote to test the eXtended TEA encryption algorithm. Compile it as "xTea" and type "xTea" on the commandline to see the usage info. It just uses a password as a key (up to 16 chars) so you're not getting the full 128bit, probably about 6.5bit/char with a normal complex password.

Block chaining is CBC, error checking is minimal, CRC32 for the file indegrity check.

Let me know if you find any glaring bugs

ADDED:
FYI, the initVector in the header is the Initialisation Vector for the chaining here http://en.wikipedia.org/wiki/Block_ciph ... _operation it's not required to be secret or secure, just different each time a key is used

Code: Select all

Structure vData
    StructureUnion
        Quad.q
        DW.l[2]
        Bytes.c[8]
    EndStructureUnion
EndStructure

Structure KeyData
    StructureUnion
        DW.l[4]
        Bytes.c[16]
    EndStructureUnion
EndStructure

Structure FileHeader
    DataSize.q      ;original plaintext size with no white space
    WhiteSpaceSize.b
    InitVector.q    ;(Random(2147483647) * Random(2147483647)) - 1
    CRC32.l
    Encryption.b  ;
    Compressed.b  ;#True / #False, future use
EndStructure

#TEA = 1
#XTEA = 2

Declare xTEA_Encrypt(*pKey.KeyData, *pDataBlock.vData)
Declare xTEA_Decrypt(*pKey.KeyData, *pDataBlock.vData)
Declare CBCEncrypt(Filename.s)
Declare CBCDecrypt(Filename.s)
Declare main()

Global Filename.s
Global sKey.s

Main()

;=============================================================

Procedure main()

    OpenConsole()
    
    If CountProgramParameters() = 2
        Filename = ProgramParameter()
        skey = ProgramParameter()
        If FileSize(Filename) > 0
            If UCase(GetExtensionPart(Filename)) = "XTEA" ; decrypt
                CBCDecrypt(Filename)
            Else ;encrypt
                CBCEncrypt(Filename)
            EndIf    
        EndIf
    
    Else
        PrintN("")
        PrintN("Usage: xTEA <File> <PassKey (16 char) >")  
        PrintN("       If input file is '.xtea' then decrypt")  
        PrintN("       else encrypt input file and add '.xtea' to the name")        
    EndIf  

    CloseConsole()
    

EndProcedure

;=============================================================

Procedure xTEA_Encrypt(*pKey.KeyData, *pDataBlock.vData) 

    Delta.l = 2654435769 
    sum.l = 0 

    ;Break 64bit data into 32bit blocks 
    v0.l = *pDataBlock\DW[0]  : v1.l = *pDataBlock\DW[1] 

    *K.KeyData = *pKey 

    For i = 0 To 31 
        v0 = v0 + (((v1<<4) ! (v1>>5 & $7fffffff)) + v1) ! (Sum + *K\DW[sum & 3] ) 
        Sum = Sum + delta            
        v1 = v1 + (((v0<<4) ! (v0>>5 & $7fffffff)) + v0) ! (Sum + *K\DW[(sum>>11 & $7fffffff) & 3] ) 
    Next 
    
    *pDataBlock\DW[0] = v0 
    *pDataBlock\DW[1] = v1 

EndProcedure 

;============================================================= 

Procedure xTEA_Decrypt(*pKey.KeyData, *pDataBlock.vData) 

    Delta.l = 2654435769 
    sum.l = 32*Delta 
      
    ;Break 64bit data into 32bit blocks 
    v0.l = *pDataBlock\DW[0]  : v1.l = *pDataBlock\DW[1] 

    *K.KeyData = *pKey 
    
    For i = 0 To 31 
        v1 = v1 - (((v0<<4) ! (v0>>5 & $7fffffff)) + v0) ! (Sum + *K\DW[(sum>>11 & $7fffffff) & 3]) 
        Sum = Sum - delta            
        v0 = v0 - (((v1<<4) ! (v1>>5 & $7fffffff)) + v1) ! (Sum + *K\DW[sum & 3]) 
    Next 
    
    *pDataBlock\DW[0] = v0 
    *pDataBlock\DW[1] = v1 

EndProcedure 

;=============================================================

Procedure CBCEncrypt(Filename.s)

    Protected key.KeyData 
    Protected vData.vData
    Protected PlainText.s = ""
    Protected CypherText.s = "" 
    Protected hFile.l
    Protected CBCBlock.q
    Protected CBCOut.vData
    Protected Header.FileHeader
              
    If Trim(sKey) = "" Or filename = ""
        ;no key, skip
    Else

        hFile = OpenFile(#PB_Any,Filename)           
            Header\DataSize  = Lof(hfile)
            *inFileBytes = AllocateMemory(Header\DataSize)
            *outFileBytes = AllocateMemory(Header\DataSize)
            ReadData(hFile, *inFileBytes, Header\DataSize)
        CloseFile(hFile)
            
        Header\CRC32 = CRC32Fingerprint(*inFileBytes, Header\DataSize )
        Header\InitVector = (Random(2147483647) * Random(2147483647)) - 1
        Header\Encryption = #XTEA
        Header\Compressed = #False

        If Header\DataSize  % 8 <> 0
            Header\WhiteSpaceSize = 8-(Header\DataSize % 8)
            *inFileBytes = ReAllocateMemory(*inFileBytes, Header\DataSize + Header\WhiteSpaceSize)
            *outFileBytes = ReAllocateMemory(*outFileBytes, Header\DataSize + Header\WhiteSpaceSize)
        EndIf    
 
        sKey = Left(sKey,16)  ;max len
        For i = 0 To Len(sKey) -1
            key\Bytes[i] = Asc(Mid(sKey,i+1,1))
        Next
   
        For i = 1 To (Header\DataSize + Header\WhiteSpaceSize) / 8
            CopyMemory(*inFileBytes + ((i-1)*8),@vData,8)

            If i > 1 ;not first block so CBC XOR                
                vData\Quad = CBCBlock ! vData\Quad 
            Else
                CBCBlock = Header\InitVector
                vData\Quad = CBCBlock ! vData\Quad 
            EndIf

            xTEA_Encrypt(@key, @vData)
            CBCBlock = vData\Quad            
            CopyMemory(@vData,*outFileBytes + ((i-1)*8),8)

        Next

        hFile = OpenFile(#PB_Any,Filename + ".xtea")
            WriteData(hFile, @Header, SizeOf(Header))
            WriteData(hFile, *outFileBytes, Header\DataSize + Header\WhiteSpaceSize)
            TruncateFile(hFile)
        CloseFile(hFile) 
        FreeMemory(*outFileBytes) 
        FreeMemory(*inFileBytes) 
            
    EndIf
EndProcedure

;=============================================================

Procedure CBCDecrypt(Filename.s)

    Protected key.KeyData 
    Protected vData.vData
    Protected PlainText.s = ""
    Protected CypherText.s = "" 
    Protected hFile.l
    Protected CBCBlock.q
    Protected CBCInit.q
    Protected CBCOut.vData
    Protected Header.FileHeader
    

    If Trim(sKey) = "" Or Trim(Filename) = "" Or FileSize(Filename) < 1
        ;no key, skip
        Debug "skipped"
    Else
        sKey = Left(sKey,16)  ;max len
        For i = 0 To Len(sKey) -1
            key\Bytes[i] = Asc(Mid(sKey,i+1,1))
        Next
        
        hFile = OpenFile(#PB_Any,Filename)
            ReadData(hFile, @Header, SizeOf(Header))
            
            *inFileBytes = AllocateMemory(Header\DataSize + Header\WhiteSpaceSize)
            *outFileBytes = AllocateMemory(Header\DataSize + Header\WhiteSpaceSize)
            ReadData(hFile, *inFileBytes, Header\DataSize + Header\WhiteSpaceSize)
        CloseFile(hFile) 
            
        For i = 1 To (Header\DataSize + Header\WhiteSpaceSize) / 8
            CopyMemory(*inFileBytes + ((i-1)*8),@vData,8);Mid(CypherText,(i*8)-7,8)

            If i > 1 ;not first block so CBC XOR                      
                CBCInit = vData\Quad
                xTEA_Decrypt(@key, @vData)
                CBCOut\Quad = CBCBlock ! vData\Quad 
                CBCBlock = CBCInit                        
            Else
                CBCInit = Header\InitVector
                CBCBlock = vData\Quad                        
                xTEA_Decrypt(@key, @vData)
                CBCOut\Quad = CBCInit ! vData\Quad 
            EndIf

            CopyMemory(@CBCOut,*outFileBytes + ((i-1)*8),8)

        Next

        If Header\CRC32 = CRC32Fingerprint(*outFileBytes, Header\DataSize)
            
            Filename = RemoveString(Filename, ".xtea")
            hFile = OpenFile(#PB_Any,Filename )
                ;WriteData(hFile, @Header, SizeOf(Header))
                WriteData(hFile, *outFileBytes, Header\DataSize ) ;+ Header\WhiteSpaceSize
                TruncateFile(hFile)
            CloseFile(hFile) 
            FreeMemory(*outFileBytes) 
            FreeMemory(*inFileBytes)
                     
        Else
            PrintN("CRC Failure, data may be corrupt")
        EndIf    

    EndIf
    
                    
EndProcedure
Last edited by pdwyer on Fri May 01, 2009 4:27 pm, edited 1 time in total.
Paul Dwyer

“In nature, it’s not the strongest nor the most intelligent who survives. It’s the most adaptable to change” - Charles Darwin
“If you can't explain it to a six-year old you really don't understand it yourself.” - Albert Einstein
Top
User avatar
Crusiatus Black
Enthusiast
Enthusiast
Posts: 389
Joined: Mon May 12, 2008 1:25 pm
Location: The Netherlands
Contact:
Contact Crusiatus Black

Post by Crusiatus Black »

So nice! I have been looking into diffirent ways of encrypting in purebasic, and i must say, this is one of the best!
Top
User avatar
Crusiatus Black
Enthusiast
Enthusiast
Posts: 389
Joined: Mon May 12, 2008 1:25 pm
Location: The Netherlands
Contact:
Contact Crusiatus Black

Post by Crusiatus Black »

For some reason it doesn't really matter what key i use for decrypting, it always decrypts...

**Edit
I checked again, and it only happens with unsafe short keys that don't really look alot diffirent.
Top
User avatar
pdwyer
Addict
Addict
Posts: 2813
Joined: Tue May 08, 2007 1:27 pm
Location: Chiba, Japan

Post by pdwyer »

Could you be more specific? if there's a bug I'd like to know.
I have a gui version of this now, not for files but for text. It's called SecPad and it's notepad that writes XTEA ".stxt" encrypted files and prompts for pwds.
Paul Dwyer

“In nature, it’s not the strongest nor the most intelligent who survives. It’s the most adaptable to change” - Charles Darwin
“If you can't explain it to a six-year old you really don't understand it yourself.” - Albert Einstein
Top
User avatar
Crusiatus Black
Enthusiast
Enthusiast
Posts: 389
Joined: Mon May 12, 2008 1:25 pm
Location: The Netherlands
Contact:
Contact Crusiatus Black

Post by Crusiatus Black »

Scenario: I encrypted a XML file using key EncKey (for testing)
then i decrypted it using that key... worked
after that i tried decrypting using a diffirent key, EncKeyll or Password

It decrypted the file.

When using larger keys, it doesn't decrypt after parsing the wrong key...

Is this my error, or a bug somewhere?
Top
User avatar
pdwyer
Addict
Addict
Posts: 2813
Joined: Tue May 08, 2007 1:27 pm
Location: Chiba, Japan

Post by pdwyer »

Thanks, I'll take a look when I get home.
Out of interest, how big was the XML file?
Paul Dwyer

“In nature, it’s not the strongest nor the most intelligent who survives. It’s the most adaptable to change” - Charles Darwin
“If you can't explain it to a six-year old you really don't understand it yourself.” - Albert Einstein
Top
User avatar
pdwyer
Addict
Addict
Posts: 2813
Joined: Tue May 08, 2007 1:27 pm
Location: Chiba, Japan

Post by pdwyer »

:o

Okay, thanks we have a bug. Only the first 4 bytes of the pwd are being used. I don't think this was the case when I was using TEA so it must have crept in at the XTEA algorithm.

Let me look at it more closely to see if I can find where it's going wrong.
Paul Dwyer

“In nature, it’s not the strongest nor the most intelligent who survives. It’s the most adaptable to change” - Charles Darwin
“If you can't explain it to a six-year old you really don't understand it yourself.” - Albert Einstein
Top
User avatar
pdwyer
Addict
Addict
Posts: 2813
Joined: Tue May 08, 2007 1:27 pm
Location: Chiba, Japan

Post by pdwyer »

:oops: :lol:

The code above should be fixed, I'm an idiot. I used the wrong data type for the key schedule and worked with 4 bytes instead of 4 longs <sigh>

up to 32bit encryption wouldn't have been too meaningful.

thanks for finding this, I have some data to re save :P
Paul Dwyer

“In nature, it’s not the strongest nor the most intelligent who survives. It’s the most adaptable to change” - Charles Darwin
“If you can't explain it to a six-year old you really don't understand it yourself.” - Albert Einstein
Top
User avatar
Crusiatus Black
Enthusiast
Enthusiast
Posts: 389
Joined: Mon May 12, 2008 1:25 pm
Location: The Netherlands
Contact:
Contact Crusiatus Black

Post by Crusiatus Black »

Thanks for solving this minor issue, hehe i like it when i get bugs like this.
They make me think "Whaaa what was i thinking"
Top
Post Reply

Return to “Tricks 'n' Tips”