Close

Anteriority

A project log for PEAC Pisano with End-Around Carry algorithm

Add X to Y and Y to X, says the song. And carry on.

yann-guidon-ygdesYann Guidon / YGDES 04/20/2021 at 18:500 Comments

This episode/project makes me really sceptical and confused. Maybe that's disarray.

I have seen that the Pisano periods have been studied for ages but I have so far never seen the algorithm that this project describes. As if it was original to even use a carry out into the carry in of additions. Or to loop over the successive results of additions, which Adler and Fletcher missed. I have found "Fibonacci hashing" but it's not related.

In fact I am already familiar with systems such as Bob Jenkins' lookup3.c which contains many additions and XORs so I didn't think it would be ground-breaking to minimise this type of system down to the purest, smallest essential ideas. I would expect this to have been already extensively studied as a primitive for other systems to build upon. I could imagine that this "primitive" is taught at the first year of secret cryptoschools, alongside LFSRs and Fiestel rounds. The Fibonacci generator is not perfect, but so are LFSRs which are so widely used instead. Maybe they could be combined ? (yes)

I feel lost, just as when I discovered the #σα code, the #µδ code, the #Recursive Range Reduction (3R), the Balanced Control Binary Trees, but I have also "rediscovered" or "reinvented" many things... And I have no idea how to find prior art or references on something that I just find, because, if it is really new, how can I know that it existed already or not ? Ignorance is not an excuse, so if you have any hint, idea, suggestion or data, please comment or contact me. I simply can't understand that such a simple system didn't exist before.

...

It is not easy to find resources about the subject of this project. When doing a websearch, entering the keywords "Fibonacci" and "LFSR" or "CRC" bring pages that compare the CRC topologies of Fibonacci vs Galois (or this very project).

I have found something quite close but the claims are shaky and the patent has been withdrawn. Look at the figure 3 of GB2377142A : it has all the elements, and even more, but organised differently. For example, the XOR is in series with the output, which introduces the weakness discussed in an earlier log. The patent addresses this weakness by adding a counter (which could/should be a simple LFSR, as in Fig. 2), and since there is no carry re-circulation, this can be considered as a simple "Pisano" checksum.

...

Update:

An astute reader pointed me to https://github.com/endlesssoftware/sqlite3/blob/master/wal.c

The SQLite software uses a similar scheme, which closely follows the Piano Magic song mantra to the letter, but with 32 bits and with no carry, it's tuned for speed and not resilience but it seems to be "good enough":

** [...] The checksum is computed by interpreting the input as
** an even number of unsigned 32-bit integers: x[0] through x[N].  The
** algorithm used for the checksum is as follows:
** 
**   for i from 0 to n-1 step 2:
**     s0 += x[i] + s1;
**     s1 += x[i+1] + s0;
**   endfor
**
** Note that s0 and s1 are both weighted checksums using fibonacci weights
** in reverse order (the largest fibonacci weight occurs on the first element
** of the sequence being summed.)  The s1 value spans all 32-bit 
** terms of the sequence whereas s0 omits the final term. 

Can you hear Glen Johnson yet ? :-D (with Y=S0 and X=S1)

Combination/mixing occurs with addition and not XOR, the difference does not seem meaningful. The lack of carry recirculation however lets me think that the missing overflow recycling reduces the "safe block length" and exposes the algorithm to a "stuck point" situation. Which is why my first idea was to use only half of the register length to keep some extra entropy out of reach from incoming data tampering.

The file's date is 2010 and I suppose there were earlier implementations but what's the earliest one ? I'll have to track the author since the name is absent...

....

Another hint and find in this thesis dated 2006:

McAuley [29] has proposed the Weighted Sum Codes (WSC) algorithm as an alternative to the Fletcher
checksum and CRC. Feldmeier [30] conducted a comparison of WSC against one’s complement addition
checksum, XOR checksum, block parity, Fletcher checksum, and CRC. He asserted that WSC is as good
as CRC in error detection and as fast as Fletcher checksum in compute speed. Because WSCs are not
commonly used, we leave an examination of that checksum to future work.

Why is this paragraph interesting ? Because the code above mentions  "weighted checksums", so "Weighted Sum Codes" or WSC might be the name previously given to this type of structure.

The thesis :

The Effectiveness of Checksums for Embedded Networks by Theresa C. Maxino

A thesis submitted in partial fulfillment of the requirements for the degree of Master of Science in Electrical and Computer Engineering
Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, Pennsylvania, USA, May 2006

The reference:

[29] A. J. McAuley, “Weighted sum codes for error detection and their comparison with existing codes,” IEEE/ACM Trans. on
Networking, vol. 2, no. 1, pp. 16–22, Feb. 1994.

Good, the date goes back to 1994 now. But if "WSC is as good
as CRC in error detection and as fast as Fletcher checksum in compute speed
", WHY are they not commonly used ?

Anyway, this good read provides some very useful graphs, such as this one that compares XOR and ADD checksums :

Asymptotic undetected error rates don't seem to go below 1% when 32-bit words are added together... Go and read the thesis for more of these graphs !

....

More weighted sum codes at :

Weighted sum code without carries — Is an optimum code with detection of any double errors in data vectors (good question)

Weighted sum codes for error detection and their comparison with existing codes (The 1994 McAuley paper is often cited)

McAuley filed at least one patent on using WSC while at Bell Labs. The patent US5526370A expired in 2014 and does not seem to cover what is studied in this project. I get the impression it performs a sort of circular rotation of the data...

.

...

Update:

I have received a personal message, which I try to translate here:

As we French say, "it's not false", but also incomplete. I will try to address each point and provide more context:

So the nuance I try to explain is that the context, the constraints, the goals, will guide the choice of an algorithm: the more we already know, the better. And there are many cases where you will simply use an existing library (particularly for sensitive applications where you can't afford a bug or a leak). But this is not always possible (for all kinds of embedded systems) and this is where knowing more primitives helps.

In the case of the 2×16bits primitive I characterise in this project, the point is that it is "good enough" for many trivial tasks where security or safety are not critical, but resources are very scarce. The "Pisano with carry" approach is a very low-hanging fruit, it is not perfect in every aspect. If you want a better result, you can combine it with other imperfect algorithms, so their defects cancel each other, like I did in 14. Moonlighting as a PRNG.

If more statistical properties are required, http://www.burtleburtle.net/bob/hash/doobs.html is a great introduction (and the whole site is a goldmine). I also remember that Bruce Schneier's "Applied Cryptography" book has in-depth analysis of LFSR/CRC and some exotic derivatives that tried to solve LFSRs' shortcomings.

Discussions