UbiCrypt Chm

What is Chiasmus?

2nd - Cryptanalysis

Chiasmus In General

That's it for the 2nd part.

Thanks! Questions?

Reverse Engineering of Chiasmus

Hands on COM

Felix Schuster

UbiCrypt Summer School, 23rd July 2013, Bochum

The GSTOOL

• Main purpose is management and risk assessment of IT landscapes according to "IT-Grundschutz"
• Cryptographic functionality is just a bonus (Extras -> Verschlüsselung...)
• key-store (including key generator)
• encryption of files
• decryption of files

1st - Reverse Engineering

• Chiasmus encryption
• 12 full rounds + prologue and epilogue
• 26 round keys of 32 bits each
• 64 bits block size
• Substitution and permutation network (SPN)
• like AES
• unlike DES (Feistel network)
• 2 bijective and inverse s-boxes GF(2)^8 -> GF(2)^8
• 2 mappings GF(2)^32 x GF(2)^32 -> GF(2)^32
• multiplication and addition modulo 2^32
• can be regarded as large s-boxes with weaker characteristics
• rather uncommon (?)

AES is 4-5 times faster

(on my old laptop,

no loop-unroll)

• 13MB behemoth
• Visual Basic 6
• 10.000+ functions
• Initial IDB is a mess
• Wasted hours/days trying to locate the crypto-algo.
• My faults:
• Didn't do any high-level analysis up-front (e.g. look for suspicious strings)
• Didn't think of COM...

• 124KB lightweight
• Visual C++ 6.0
• 809 functions
• Some suspicious strings...
• ... but no smoking-gun-exports

=> COM in-process server (defines and implements the GSTOOL's custom ICrypt interface)

The ICrypt Interface

The Component Object Model (COM)

The Chiasmus key-schedule

• Derives 26 round keys of 32 bits each from 160 bits input key.
• First 4 round keys (4*32 bits = 160 bits) are equal to the input key.
• Last 21 round keys are calculated from the first for round keys:

• "COM is a platform-independent, distributed, object-oriented system for creating binary software components that can interact. COM is the foundation technology for Microsoft's OLE and ActiveX technologies." - MSDN

• A COM server provides certain classes to other applications in a programming-language agnostic way.
• Normally a COM server registers itself under a unique CLSID in the registry:
• {420EAF50-0869-4F1F-9E4D-B2DCEC175208}
• Windows 8 apps are COM servers.
• We can easily interact with COM servers using a variety of ways:
• PowerShell
• C#
• ...

srand(time())

:D

Chiasmus In GSTOOL

... and ECB mode is used.

• Key generation
• Each of the 20 key bytes is generated by a simple call to rand().
• Seed is set once through srand(time()).

• Key complexity
• rand() taken for itself: 32 bits
• rand() with srand(time()): ~24.91 bits for 1 year period, ~28.23 bits for 10 year period
• Already easily brute-forcable within seconds/minutes but can be reduced further...

Visual C's rand() implementation (linear congruential generator):

GSTOOL's key generation only uses the 8 lsbits and throws away the 8 msbits of each rand() invocation.

The upper 8 bits of the LCG's internal state do not need to be taken into account.

=> Complexity can be reduced to 24 bits from initially 160 bits.

=> Overall key space consists of only roughly 17 million keys!

=> Every encrypted file can be decrypted in 2-3 seconds on this laptop.

Linear Cryptanalysis

Differential Cryptanalysis

Walsh Coefficients Chiasmus s-box

Walsh Coefficients AES s-box

Difference Distribution Table Chiasmus s-box

Difference Distribution Table AES s-box

Walsh Coefficients randomly chosen sbox

Difference Distribution Table randomly chosen s-box

• Quality measure for s-boxes: How big is the chance that the sum of certain input bits is equal to the sum of certain output bits in GF(2)?
• The maximum "Walsh Coefficient" is measure of quality
• AES and Chiasmus sboxes both have an optimal maximum Walsh Coefficient of 32, whereas the random sbox has maximum Walsh Coefficient of 72.

• Quality measure for sboxes: How big is the chance that the difference dX of two input bytes X' and X'' is equal to the difference dY of the two corresponding output bytes Y' and Y''.
• dX = X' xor X''
• dY = Y' xor Y''
• To my knowledge both the AES and Chiasmus s-boxes are optimally strong.

Discussion

• The AES s-box represents an inversion in GF(2^8) and a subsequent affine mapping in GF(2)^8.

• Currently this is apparently the only known way to construct an sbox with optimal properties.

• It can be shown that the Chiasmus s-boxes are constructed differently than the AES s-boxes.
• I.e. there exists no combination of any inversion in GF(2^8) that in combination with any affine mapping in GF(2)^8 constructs the Chiasmus s-boxes.
• This does not mean though that the BSI knows a secret way to construct optimal s-boxes.
• Probably there is just another affine mapping before the inversion applied.

Conclusion

• Chiasmus appears to be well constructed and modern.
• Its implementation in GSTOOL is broken.