Document: Leopard14/L14 Security Analysis Author: Robin Carey Date: 13th Aug 2003 Revision: 1 Introduction ============ This document is a short text-file which summarizes my security analysis of Leopard14/L14. It does not deal with the KSA (Key Schedule Algorithm). The Basics ========== The security of L14 is based on the difficulty of knowing where any value is in the internal state, and also from not knowing which element of the internal state is picked as an output. Since two unknown elements of the internal state are swapped per byte reported (most of the time), an adversary never knows which elements of the internal state are changing. L14 Security Analysis ===================== When I was checking L14 for security weaknesses, the first thing I did was check what happens when a double is produced, and also, what happens when "x" equals "y"; since these are identifiable events from which a security weakness may be present. What happens when a double is produced is simply that the same unknown element of the internal state is picked twice (and sometimes thrice) as an output. Thus, there is practically zero leakage of information when this happens: -- [ 67431 ] x= 30, y= 91, sx=220, sy=139, z=103, sz=146 [ 67432 ] x= 31, y= 90, sx= 10, sy= 93, z=103, sz=146 DOUBLE [ 67433 ] x= 32, y= 89, sx= 21, sy=237, z= 2, sz= 57 -- [ 67473 ] x= 72, y= 49, sx=159, sy=214, z=117, sz=234 [ 67474 ] x= 73, y= 48, sx= 23, sy= 94, z=117, sz=234 DOUBLE [ 67475 ] x= 74, y= 47, sx= 47, sy=242, z= 33, sz=239 -- [ 67716 ] x= 59, y= 61, sx= 99, sy=137, z=236, sz= 75 [ 67717 ] x= 60, y= 60, sx=118, sy=118, z=236, sz= 75 X EQUAL Y DOUBLE [ 67718 ] x= 61, y= 59, sx=137, sy=124, z= 5, sz=123 -- [ 68022 ] x=109, y= 10, sx= 58, sy=229, z= 31, sz=198 [ 68023 ] x=110, y= 9, sx=169, sy=118, z= 31, sz=198 DOUBLE [ 68024 ] x=111, y= 8, sx= 88, sy= 75, z=163, sz= 64 -- [ 68098 ] x=185, y=189, sx=105, sy= 29, z=134, sz=137 [ 68099 ] x=186, y=188, sx=152, sy=238, z=134, sz=137 DOUBLE [ 68100 ] x=187, y=187, sx=166, sy=166, z= 76, sz=186 X EQUAL Y -- [ 68305 ] x=136, y=238, sx= 33, sy=210, z=243, sz= 30 [ 68306 ] x=137, y=237, sx=162, sy= 81, z=243, sz= 30 DOUBLE [ 68307 ] x=138, y=236, sx=250, sy=150, z=144, sz= 2 [ 68308 ] x=139, y=235, sx=143, sy= 1, z=144, sz= 2 DOUBLE [ 68309 ] x=140, y=234, sx=137, sy=162, z= 43, sz=217 -- [ 68948 ] x= 11, y=104, sx=132, sy= 74, z=206, sz= 38 [ 68949 ] x= 12, y=103, sx=123, sy= 83, z=206, sz= 38 DOUBLE [ 68950 ] x= 13, y=102, sx=226, sy=127, z= 97, sz=194 As you can see from these statistics, the only information that is leaked is that "x" has been incremented and "y" has been decremented to adversary-unknown values, and also that "sx" + "sy" equals the same unknown value ("z") for both consecutive outputs. So there is no ``way in'' for an adversary via the phenomenon of doubles. As for the case of "x" == "y"; [ 15727 ] x= 56, y= 56, sx=197, sy=197, z=138, sz=149 X EQUAL Y [ 15855 ] x=184, y=184, sx=173, sy=173, z= 90, sz=189 X EQUAL Y [ 16238 ] x= 55, y= 55, sx=125, sy=125, z=250, sz=128 X EQUAL Y [ 16366 ] x=183, y=183, sx= 18, sy= 18, z= 36, sz= 34 X EQUAL Y [ 16749 ] x= 54, y= 54, sx=162, sy=162, z= 68, sz=208 X EQUAL Y DOUBLE [ 16877 ] x=182, y=182, sx=116, sy=116, z=232, sz= 94 X EQUAL Y [ 17260 ] x= 53, y= 53, sx=146, sy=146, z= 36, sz=159 X EQUAL Y [ 17388 ] x=181, y=181, sx=158, sy=158, z= 60, sz= 7 X EQUAL Y [ 17771 ] x= 52, y= 52, sx= 87, sy= 87, z=174, sz= 77 X EQUAL Y [ 17899 ] x=180, y=180, sx=173, sy=173, z= 90, sz=233 X EQUAL Y [ 18282 ] x= 51, y= 51, sx= 95, sy= 95, z=190, sz= 20 X EQUAL Y As you can see from these statistics, there is no information leakage at all (Note: this was the security hole discovered in L13; fixed in L14). If you carefully check the counter on the left hand-side, you will see that there is a periodical pattern: 128, 383, 128, 383, ... Most of the time when "x" == "y" a different element of the internal state is picked from the previous selection (as you can see above). But sometimes the same element is picked twice consecutively, and thus when this happens, an adversary is able to determine that "x" == "y" == some-unknown-value with high probability. So, the only possible danger arising from the case of "x" == "y", is that an adversary may be able to determine when in the output sequence the internal condition of "x" == "y" occurs. But they do not actually know what the value of "x"/"y" is, and therefore this does not pose a security problem; it is simply undesirable. But the other identifiable event which I have closely checked is what happens to "sx" and "sy" when x passes y; [ 52 ] x= 69, y= 91, sx=138, sy= 59, z=197, sz= 63 [ 53 ] x= 70, y= 90, sx=253, sy= 94, z= 91, sz= 59 [ 54 ] x= 71, y= 89, sx=200, sy=164, z=108, sz= 62 [ 55 ] x= 72, y= 88, sx=246, sy= 76, z= 66, sz= 50 [ 56 ] x= 73, y= 87, sx=163, sy= 18, z=181, sz=150 [ 57 ] x= 74, y= 86, sx=187, sy= 10, z=197, sz= 63 [ 58 ] x= 75, y= 85, sx=252, sy=244, z=240, sz=185 [ 59 ] x= 76, y= 84, sx=222, sy=241, z=207, sz=193 [ 60 ] x= 77, y= 83, sx= 30, sy= 53, z= 83, sz= 53 [ 61 ] x= 78, y= 82, sx= 24, sy= 37, z= 61, sz=170 [ 62 ] x= 79, y= 81, sx= 97, sy= 7, z=104, sz=117 [ 63 ] x= 80, y= 80, sx=243, sy=243, z=230, sz=140 X EQUAL Y [ 64 ] x= 81, y= 79, sx= 7, sy= 79, z= 86, sz= 10 [ 65 ] x= 82, y= 78, sx= 37, sy=168, z=205, sz=109 [ 66 ] x= 83, y= 77, sx= 53, sy=121, z=174, sz=224 [ 67 ] x= 84, y= 76, sx=241, sy=123, z=108, sz= 62 [ 68 ] x= 85, y= 75, sx=244, sy=245, z=233, sz= 89 [ 69 ] x= 86, y= 74, sx= 10, sy=248, z= 2, sz=169 [ 70 ] x= 87, y= 73, sx= 18, sy= 47, z= 65, sz=204 [ 71 ] x= 88, y= 72, sx= 76, sy=123, z=199, sz= 8 [ 72 ] x= 89, y= 71, sx=164, sy= 49, z=213, sz= 72 [ 73 ] x= 90, y= 70, sx= 94, sy= 84, z=178, sz=226 [ 74 ] x= 91, y= 69, sx= 59, sy=223, z= 26, sz= 31 As you can see from the stats, there is a mirror image of "sx" and "sy" around the point where "x" passes "y"; but only one value stays constant. In this example the values which stay constant are: 7, 37, 53, 241, 244, etc. So this is an area of possible weakness. However, because only one value stays constant, the other value "makes up for it", i.e. around the point where "x" passes "y" the non-constant value ensures that the security requirement that _any_ unknown value of the internal state is picked, holds. As we move further and further away from the point where "x" passes "y", more and more elements of the internal state have been swapped/changed, and thus this statistically weak area of the output sequence fades away. So for example, 50 outputs after the crossing point about 100 elements of the internal state have changed/swapped and thus this "weak fuzzy area" has dissipated. It is possible that this statistically weak area may be identifiable using some algorithm, and therefore it is possible that an adversary may be able to isolate the internal crossing point of "x" == "y". But again, this is not a security problem; just undesirable. The only security checks which I haven't made so far are for the more complicated problems such as fortuitous states and predictive states; these are problems which were discovered in ARC4 and which may or may not be present in L14. I'll try and get around to it sometime.