New results on reduced-round Tiny Encryption Algorithm using genetic programming

Authors: Karel Kubicek, Jiri Novotny, Petr Svenda, Martin Ukrop

<note tip>This paper is not published yet, therefore page is not yet finalzed</note> Abstract: Analysis of cryptoprimitives usually requires extensive work of a skilled cryptanalyst. Some automation is possible, e.g. by using randomness testing batteries such as Statistical Test Suite from NIST (NIST STS) or Dieharder. Such batteries compare the statistical properties of the function’s output stream to the theoretical values. A potential drawback is a limitation to predefined tested patterns. However, there is a new approach – EACirc is a genetically inspired randomness testing framework based on finding a dynamically constructed test. This test works as a probabilistic distinguisher separating cipher outputs from truly random data. In this work, we use EACirc to analyze the outputs of Tiny Encryption Algorithm (TEA). TEA was selected as a frequently used “benchmark” algorithm for cryptanalytic approaches based on genetic algorithms. In this paper, we provide results of EACirc applied to TEA ciphertext created from differently structured plaintext. We compare the methodology and results with previous approaches for limited-round TEA. A different construction of EACirc tests also allows us to determine which part of cipher’s output is relevant to the decision of a well-performing randomness distinguisher.

• Journal page: Infocommunication journal
• Download author pre-print of the paper: pdf
• Download used version of EACirc tool and configuration files: zip source code, executable file

Bibtex:

 @inproceedings{secrecyamplif_wistp2015,
   author = {Radim O\v{s}\v{t}\'{a}dal \Petr \v{S}venda \and V{\'a}clav Maty{\'a}\v{s}},
   title = {On Secrecy Amplification Protocols},
   booktitle = {The 9th WISTP International Conference on Information Security Theory and Practice (WISTP’2015),
   LNCS 9311},
   year = {2015},
   pages = {3--19},
   doi = {10.1007/978-3-319-24018-3 1},
   publisher = {Springer}
 }

- update to this paper

The secrecy amplification protocol provides description how messages with a fresh key material should be propagated inside a target network to provide secure link key to nodes with key currently compromised by an attacker. As wireless networks running on batteries are targeted, not only protocol's success rate (number of newly secured links), but also message overhead (significantly impacting energy consumption) must be considered.

A secrecy amplification protocol can be pretty effective: a network with 50-70 % of compromised links can be turned into network with 95+ % secure links for the price of small hundreds of messages (per node) in only tens of seconds.

In this we paper, we:

• Gave motivation, why secrecy amplification protocols should be used – if enough neighbours are available in network and random compromise pattern is assumed, network with only 30 % secure can be turned into network with more then 95 % secure links.
• Provided survey of all published secrecy amplification protocols (13 in total).
• Established upper bound of secrecy amplification protocol success rate for given network.
• Compared protocols wrt message efficiency, number of links they are able to secure and other characteristics.
• Discussed how hard is to execute secrecy amplification protocol in practice on real node (TelosB, TinyOS).
• Introduced new class of hybrid secrecy amplification protocols, which are easier to synchronize and provide very good tradeoff between number of secure links (higher the better) and messages transmitted (lower the better).

Figure showing increase in the number of secured links after secrecy amplification protocols in the random compromise pattern on network with 20.3 legal neighbours on average. With in- creasing number of neighbouring nodes the general effectiveness of protocol grows. As can be seen, a strong majority of secure links (> 90%) can be obtained even when the initial network had 70% of compromised links.

Figure showing increase in the number of secured links per message used during the protocol execution (random compromise pattern, 20.3 legal neighbours on average). The higher value is better - more links are secured per single message. Node-oriented protocols send significantly more messages with rising network density making them less effective per single message. This stands especially for 4-party node-oriented protocols, which are the least effective. The best tradeoff shows group-oriented and hybrid protocols.