Introducing nonces again for session resyncs ...

Just thinking loud ...

I've just realized that the sequence counter used as nonce can be reintroduced again in ++æ but achieving nonce resistance to repetitions just keeping internally the last counter used and rejecting the call (either for Enc or Dec) if the new counter passed is not greater. This way a loss tolerant communication could accept the lost of some message(s) and go on with the same session wo requiring to negotiate a new session key ...

Now this approach permits the use of a nonce to resynchronize loss tolerant exchanges but avoids the typical problems with nonce repetition just introducing a small status vector in the algorithm ... it sounds good =)

I'll try this way If I can find the time to write down a specification for ++æ v2.0 some day ... ;)

++æ v2 candidates with renewed AD processing (Nov. 5th 2014)

I have drawn some diagrams illustrating the idea of proccessing AD exactly in the same way than the cryptogram. This approach fixes the flaw identified by Daniel Bleichenbacher in the initial draft design of the three ++æ v2 candidates that allowed to replace sequences of 3 AD blocks with the form ...||X||Y||Y||...  by just ...||Y||X||X||...

Click here

This new approach would provide the same integrity security for AD than for the cryptogram sequence.

Moreover, the sequence numbering / nonce used for session resynchronization has been eliminated and the candidates operate purely in stateful mode. This way operation is simplified and it is made robust against any counter / nonce misuse. The paid price is that in order to resynchronize both communicants it is required to set a new session key.

++Æ can be freely used

I have formally withdrawn all the patent claims covering all the ++æ variants so far published either offically as CAESAR candidates (i.e. versions 1.1 and 1.2) or in this blog as  v2.0 candidates . Moreover, to the knowledge of the author, no one of them is covered by any other IPR restriction. Thus, anyone willing to further develop any of them, or to use, is free to do so (and welcome).

Cheers !

(to be continued?)


September 28th, 2014 Update:

Daniel Bleichenbacher raised a flaw in the proposed scheme for Associated Data: any triplet ... || x || y || y || ..., in the AD string can be replaced by ... || y || x || x || ... and the modification will not be detected. A silly mistake of me :(

I suppose it can be easily fixed somehow (in fact, I'm tempted to post some simple solutions) but I wont it do by my own. Working in a solo team and devoting only a fraction of my spare time makes me unable to consolidate a v2.0 for ++æ. In any case, I found some fun and beaty during this exercise with Fibonacci sequences applied to AE and I'll go on, at a slower pace and only for my eyes by the moment, with some funny concept in this line for a even much simpler AEAD scheme ...

October 21st 2014 Update

... just to write down that a generalized sound approach would be to handle the AD data in the same way that cryptogram blocks when processed by the authenticated decryption algorithm ... If i find some time I'll update some day the corresponding diagram specifications for the three ++a2 v2.0 candidates ...

Current progress on candidates for ++æ v2.0

While looking for ++æ definite design, many schemes have been on the table for a while and a few of them endured as good AEAD candidates. The three ones presented in the link below are the most interesting ones identified so far:

Link to ++æ v2 candidates

While these  ++æ v2 candidates are still based on the target concept of combining a very few xor/arithmetic sums with each call to the block cipher algorithm as the v1, their security is not as much based on the non-linear combination of the two sums types (althought it maintains an important role). Now, security grants are more based on block chaining based on one of the simplest and better known linear recurrences: generalized (i.e. initialized with 2 arbitrary values instead of the classical 0 and 1) Fibonacci sequences are used to propagate in a linear, but chaotic, way the deciphering process of one block to the subsequent ones. There are two candidates (1st and 3rd) that exhibit very good properties but one is not parallelizable for decryption and the other adds 6 sums to each block cipher call. On the other hand, the 2nd one is fully parallelizable and uses just only 3 sums per block but its security properties require further assessment.  

After studying the behaviour of the randomized Fibonacci modular sequences, I'm pretty sure the 1st and 3rd candidate are highly strong and I would like to build security proofs for them and to complete the assessment of the 2nd variant. Unfortunatelly, being a solo team and working profesionally in very different matters I have just very scarce spare time to spend and it is almost impossible for me to complete the work.

Frankly, coming out with a final ++æ v2 design and security proof would require the collaboration of someone interested in sharing the work (and the intellectual propierty rights: the design of above ++æ v2 candidates is covered under a patent claim applicable in the same terms that published for ++æ v1). If there is any volunteer out there ... I would be delighted to know ... (I'm reachable as frecacha at gmail dot com).

Weakness in currently published ++æ versions

Lear Barack identified what seems to be the most significant weakness in ++æ v1.0 and v1.1: when the plaintext contains long runs of 1s then the inner vectors Ii / Os crystallize and just after a very short series of blocks injecting those 1s in the plaintext  (only 4 blocks in fact) the series become periodic allowing, basically, cryptogram forgery by simply removing the blocks comprised between the repetitions.

Thanks Lear for your interest and analysis! Could it drive ++æ several floors upstairs ?

Success  usually is a momentary state between long failure runs (that fortunately can be socially extended by the obtained status-quo   ;o)

Therefore, since success is now closer, I'm exploring simpler forms of addition-and-xor sums combinations that could be simpler to be analyzed, stronger in front of practical and theoretical attacks and ... even less computing demanding. A truly challenge and a truly fun game (at least while the underneath failure does not become evident ...  ;o)))

If I followed my impulses, I would post now what I have in mind as a final ++æ version, but this time I want to be more cautious and I'll wait a sound security analysis is completed before releasing any detail. For that purpose, collaborators providing independent critical reviews would be really helpful and appreciated (specially if the review comes in the form of a definite ++æ security proof ...   ;o)

(to be continued ... or not ...)

++AE v1.1

++AE v1.0 padding for both associated data and plaintext have been fixed in v1.1. Moreover, the sections of the spec doc have been aligned with CAESAR call trying to comply with all the formal requirements.

++AE v1.1

(With differences compared with v1.0)

Working on ++AE ...

The binary recurrence sequences in ++AE are performing very well. Just to illustrate it, periods frequencies, F, tested for 2^b random initial values with b= 4 ... 25 were (F(2^b), F(2^(b-1), F(2^(b-2), ...):
4
(7, 4, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
5
(17, 8, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
6
(33, 23, 6, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
7
(68, 41, 17, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
8
(121, 101, 27, 5, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
9
(253, 197, 43, 17, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
10
(527, 381, 87, 22, 6, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
11
(1051, 751, 190, 42, 10, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
12
(2070, 1519, 379, 101, 17, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
13
(4108, 3021, 798, 204, 42, 12, 5, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
14
(8144, 6129, 1547, 431, 103, 21, 5, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
15
(16292, 12385, 3081, 748, 199, 45, 15, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
16
(32662, 24717, 6111, 1538, 378, 107, 16, 6, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
17
(65765, 48942, 12281, 3061, 757, 206, 49, 8, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
18
(131052, 98458, 24518, 6080, 1546, 363, 88, 31, 7, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
19
(261862, 196868, 49090, 12320, 3087, 790, 204, 47, 15, 2, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
20
(523837, 393170, 98402, 24799, 6213, 1648, 373, 111, 20, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
21
(1048610, 786413, 196579, 49194, 12314, 3026, 769, 197, 38, 8, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
22
(2095381, 1574455, 394145, 97858, 24303, 6125, 1537, 384, 90, 19, 6, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
23
(4195777, 3144412, 786326, 196698, 49047, 12241, 3093, 760, 187, 47, 15, 3, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
24
(8388922, 6291443, 1572375, 393071, 98404, 24658, 6250, 1582, 381, 95, 25, 8, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
25
(16774802, 12586845, 3143635, 787335, 196626, 48835, 12317, 3034, 753, 197, 45, 7, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

++AE goes to CAESAR

I have just submitted to CAESAR a lightweight parallelizable AEAD based on xor and modulo 2^b + sums called ++AE. Click on the diagram below for ++AE description.

As the diagram makes evident, only 4 sums per block + 1 cipher extra call per message are required by ++AE, plus 2 sums per associated data block.

I now that many sound designs will be submitted to CAESAR, and ++AE has now a reallly challenging process in front of it. I want to express my best wishes to all the authors competing (and specially to ++AE one ;-)

28th Feb 2014 - IOC will not go to CAESAR

After thinking over submitting IOC to CAESAR competition I have decided not to do so ... Meanwhile, a parallelizable and more robust AEAD mode has emerged applying the same principles ...

A long time ago in a galaxy far, far away from where my occupations are today, I did a Phd Thesis on Information Security in 1996 which most interesting product was an invention I called IOBC. IOBC was basically what is nowadays called an Authenticated Encryption Mode that intended to guarantee confidentiality and integrity for the data to be protected spending approximately just the same processing resources for each involved bit than the required to provide either confidentiality or integrity by the state of the art algorithms available by then.

Although IOBC may become a little bit obsoleted today by other AE modes that appeared in the field, I'm proud of this IOBC invention because, perhaps, it was one of the first AE modes with such characteristics that was ever proposed. Unfortunately, I abandoned this line of work during the same 1996 when I leaped from the academic world where I was teaching  by then to the exercise of my profession, Telecommunication Engineering, in the private sector.

With this blog I tried from 2011 to expand the limited dissemination IOBC received in its moment: it was just published as part of my Phd Thesis and presented during "IV Reunión Española Sobre Criptologia" (RESC1996) organized by University of Valladolid in 1996. For such purpose, I include bellow some links to the documentation produced then (partially translated to English from Spanish) and a cryptanalysis performed recently by Chris Mitchell from Royal Holloway / University of London.

IOBC Basics (click here)
The slides I presented in RESC1996 translated to English.

IOBC Explained (click here)

The paper that was published in RESC1996 Proceedings translated to English.

Complete analysis (click here) - in Spanish

The related Thesis Chapter in Spanish.

 

2013 Cryptanalysis by Chris Mitchell (click here)
After Chris analysis in February 2013 it comes that a forgery attack trying to modify an authentic cryptogram has a success probability around  2^-(b/3) instead 2^-(b/2) as I estimated in 1996, being b the corresponding block size of the used encryption algorithm. Although his result was a little bit disappointing for me, I really enjoyed collaborating and discussing with Chris on IOBC details. I wish to be able to come back with a "Reloaded" IOBC in some future. Chris: come prepared, next time I'll win the game ;-)

Comments and questions will be welcome (email address within the documents linked above)

Francisco Recacha ©2011, 2012, 2013.