A Special Class Of Stream Cipher Backdooring Techniques

remaining so cryptography is always a difficult topic but I would like to present a very hidden issue about back door and we'll explain at the end way it is a very concerning topic because a lot more nation state try to weaken cryptography and speak more and more of backdoors and we will see one application of Victorian techniques in what I call wiki strong key systems so I probably spoke of this agenda if I'm going to present one more algorithm which contained a back door which comes from original research but based on the analysis of non non case of backdoor in military equipment sold to different nation-state and everything has been revealed in 1995 and now it should be

should be now so just for you to understand where I come from I was from a military cryptanalyst so I saw a lot of different crypto machine and most of them sold to government contain more or less backdoors so I study for many for many years the concept of backdoor I'm still doing it and I try to not to promote backdoor you are not mistaken but just two to one that it is possible so let us first to explain the context you must be aware of the fact that still nowadays it is selling cryptography is very strictly control at the international level so you are formally it--i and now you have the person our agreement and you should read the sooner

agreement because in the list for B they say if you are not allowed to sell symmetric cryptography whiskey size exceed 64 bits 64 bits so read the vasana argument and the vassal argument in fact refer to weapons and dual-use technology a control it means that quickly cryptography and cryptographic algorithm are considered as weapon so how to control first you can consider implementation backdoors and we have plenty of examples since the Snowden leaks but slightly before and now we know that most nation state USA of course but China probably and Russian Russia as well try to control cryptography in a way or another and of course the environment operating systems protocols the way to code the

cryptographic API everything is interesting in order to enforce and to input implementation vectors the program that if the backdoor that implementation level the attackers can find them and of course exploit them the most difficult level is underneath and to consider mathematical backdoors directly at the mathematical description or design of the algorithm once again there are a lot of not a lot if you example variable you can refer to the case a Swiss company was selling crypto machine for government the governmental needs to nollie 130 countries and the world organization of course Switzerland is a neutral country a cheese and chocolate but in 1995 it has been revealed that most of these crypto machine web backed

by the NSA it means that during only 50 years the USA were controlling all the encrypted traffic so nearly 130 countries literally diplomatic a commercial and so on most more recently you have probably heard about the key generator sold by the Earth's I company and sudden as revealed that when they say pay 10 million dollars in adult in order to weaken twin truth backdoors in the protocol by choosing careful constant in the do a dual addict observe random number generator so there are extra there are only very few open research in this area it is clear from indirect information that NSA and English from GCHQ are working on this list of this probably was a China and

many other countries depending on their mathematical skills so the big question the key question is can we trust for any encryption algorithm it should be a national issue most of the encryption algorithm we use are not selective are chosen by all countries so once again my research is those to promote backdoor in encryption systems it quite the contrary but you must be aware of the fact that detecting backdoors is is quite an impossible you have doubly exponential complexity so I have chosen from a near the reverse approach just to prove that it is possible to embed web and today I will consider the case of string cipher stream ciphers in fact more and more we

use AES block ciphers in and so on but stream cipher did not disappear at all in fact they are still widely used in international communication in telecom Asian standards for value are 3gb PE or you have European system tetra we still use stream cipher unconvinced with the rise of IOT stream cipher will be more and more used for minimi region in which I will present a few of them in the Philip military cryptology or government Akrotiri contrary to what we may expect in fact they are still widely used because they offer better mathematical truth the security both at the implementation level but also at the operational management of the encryption system and of course industry

illumination the main problem that most of the time they are embedded in system they are proprietary and we don't know the design the one among the most recent recent example was equipped to one knife fare algorithm was being extracted by the customer in starbug from the solution and it was weak once it has been revealed the algorithm as proven to be which suits are very interesting book if you consider the implementation in terms of logic gates they are less expensive easier to implement out go faster so the didn't disappear Puritan what about the previous world back door so they're only very very few the first part in fact you have Gerald backdooring take it as a mathematical

level but also pop up schemes have been broken or were too weak to be to be used and on a practical basis two years ago for the first time with published AES like algorithm with 128 bit of key and the algorithm is fully public he's fully compatible to all the cryptographic requirement internal security but there is a algebraic and community backdoors and we are able to break it in naughty seconds with only 300 kilobyte of data so for block ciphers were proven that it was possible of course we have chosen one technique among possible other ones but it is possible on strict strength cipher backdooring since it was more related to liquid material world there

are only they are not very there are not a lot of studies maybe the crypto when my fir case is the only one I have in in mind what is important when you buy cryptographic algorithm you try to input a lot of data and to evaluate the statistical properties it is what the client can do so the first requirement that from a statistical point of view must be compliant with all this as a standard regarding crypto basic so last year we published the first string cipher no Lee it was 128 bits of key and right here is a different parameter you need to to break it but can we go further and design more sophisticated back dogs so

what the difference the main difference between block ciphers and stream ciphers is very important to keep this in mind [Music] once again from a mathematical point of view and of course industry point of view stream SIA are very simple very we have large Cerreta call corporate about the different primitives as well as the industry implementation stream cipher are used for nearly 70 years it for block ciphers it's gnarly 40 years so there is a big difference they have a pro community community or complexity means that the set of all the different possible internal states are far more limited that in block sizes so it's very difficult to ID backdoor at least seemingly so most of

the design require the algorithm to be non public and contrary to block cipher most of them are effectively if you consider block ciphers there are more complex the number of internal States is so huge yet you can even you cannot even describe them so you are it is a combinatorial nightmare so the other question is and we gave recently an answer is it possible to I something it is possible to analyze exhaustively the real answer is of course yes and you can publish the algorithm without revealing the backdoor your job to make sure that it will won't be possible to extract it so after having presented the context I would like for us to describe the

algorithm I am design just to illustrate special class a special regarding terrorism but the way to attack it so it is a stronger variant of the algorithm published last year so very classical design you are for linear feedback shift register yeah with initial content is a secret key you have a combining a boolean function which is modified at the key set up by part of the secret which it produces a random sequence which is combined by soul bitwise so to the plaintext so once again very classical design used in many many systems so the key is 128-bit so it is a master key you can of course add session key if you want but very

important in the communal combination function is modified by the keys so there are as many algorithm are the artists which isn't which is seemingly very interesting because it makes all existing cryptanalysis techniques very diesel or not to say impossible to apply in fact it is not the case so you have the multi mode with a feedback feedback polynomial there are very dense what this you expect you use and you have the initial value which is from a cryptography point of view a good value [Music] so the algorithm is very simple very classic a classical once again and you just from the key setup you modify you initialize a convening function you modify it with your function and then

you can quit and in the fact that you saw the output of the first region is just to improve as much as possible the statistical properties well once again very classical it is just a general scheme you can do a lot of things this design was deeply used during the 80s and the 90s encryption in the world it is probably still the case [Music] you can change the feedback polynomials boolean function you can do a lot of parents so the plenty plenty of possible algorithm variants which makes this general design very interesting and can be extended to many many different cases in fact this scheme of course as a back door we are going to see why but when I

compare my algorithm to previous algorithm well there are some similarities because of course I will in pile inspired by it what I have seen in my personal life the main differences that I just extend the parameters in the 80s 90s secret key was about 64 80 bit now of course it will be too short so I have just extended the design in order to would say modern key size so 128 is in the minimum of course breaking 64 bits algorithm will be rather easy now with present-day computing resources so if we look at the algorithm from the kryptonite's point of view you want to evaluate the algorithm is there any weakness no all the feedback column all our primitives we

are co-prime is degree is prime so everything everything is perfect [Music] compared to web expects the theory but theory is only theory of course the main things you have to do is to be sure that the statistical property is nearly perfect you cannot predict the future you know you cannot go backwards to the past and everything must be perfect so the algorithm has been evaluated using the US National Institute of Standards and Technology it means that when you want to design a system you are first to prove that it is FIPS 140 row compliant in fact this standard is a set of statistical tool and you have to prove that your system is a perfect from this respect my

algorithm is totally perfect of course are also standards from the academic world of the industry world the to order standard artist you I and die harder with respect to all these three eversion tool for the statistical property well ESA to is perfect of course it is a fish it is necessary condition but not sufficient condition that's why when when you have a commercial ad saying okay we are FIPS 140 row compliant well it doesn't mean that it is indeed very strong so now we have described the algorithm let the CEO to break it I'm sorry it is necessary to do a little math but you can bypass and go wait for the final result so first I have to

explain that when you want to break an algorithm result ESA won a BAC - it is precisely the reason way of design this algorithm just to illustrate that way you can perform cryptanalysis somehow different from the general perception of the academic world in the academic world they try to find one general algorithm to break all possible keys that's beautiful that very stimulating to the spirit but sometimes it's quite impossible and here it's particularly impossible generally if you want to do real-life crypt analysis you are going to divide your program in the polynomial con table a finite number of seven instance easily each instance is weak so you have not only one cryptanalysis program but a

given number with parallel computation is not a problem nowadays so in this case we just consider the 256 possible value that modified the boolean function as a particular instance so we have to run 256 programs in power that's not a problem when you are big company or an intelligence service the other difference when you work in military world we don't exceed you don't expect to break all the traffic but at least for example you are able to break let's say 10% 20% of a traffic it's a big result it was 10% of 20% of the diplomatic traffic you can learn very very much so once again operational people accept not to be able to do break everything but

the significant part of everything surely academics are considering known plaintext cryptography cryptanalysis what it's very surprising sometimes they support that they know a huge amount of plaintext in the in this case what do they need to do Krypton is real life to change this you have only access to the ciphertext it is the only thing that you can why of that or its drops so in this case I will explain to you how to work only with ciphertext so these are the side with the maths so in fact when you have a boolean function you try to measure the correlation between the input and up the basic idea is to find correlation that can enable to get rid

of of the of the boolean function just to have linear equations so for that we use a mathematical tool called world's transform so you compute in fact the correlation between a selection of input with the function and when you have the value of the correlation you are able to compute the probability that the input is equal to the output it's more simple that you that the materialization make 0 so for each possible selection of input you are what we call the spectrum it means the different correction values and what is in very important the number of one in the mask selection map of the input describes the number of register the input register you have to break

through an exhaustive search and of course we try to at the lowest possible weight of the different masks so in ok we are in for when we modify the boolean function in fact we get different award spectrum in this case for example whether if I modified with exact value d9 I get the reason this resulting function and you have here the world spectrum when you have zero it's not a good news because you have strongest value the average value being for what does it mean from a practical point of view it means that you have a very strong correlation between the input and output when you have aid it means 75% which is huge and well 462 0.62 profit

which is also huge so until now since we are able to approximate the boolean function with linear equation you can write your output as a linear combination of your beauty yes it will be too simple because we have another issue to deal with see we work with ciphertext cryptanalysis we do not we do we know about the size of the plaintext but from a new person point of view you can get some main statistical parameter for example when you were on European traffic a Western traffic you know that it will be most of the time ASCII coding or ccitt - if you go through a satellite you know the including and you know at least encoding

is a linguistic group and you can we have different tables it is an impossible to guess a general parameter which is probability for plain texts or plain text bit to be equal to 0 that's enough we don't need anything and of course we at least or Arabic languages as ethic languages and very conservative value is a 45 percent for a plaintext bit to be continued that's enough so in fact we have just to include this additional noise coming from the plaintext to or correction value you have here's a general equation it means that at the end we have a resulting total correlation of the 52% of the 51 person which is once again very good when you perform crypt

analysis so we get rid of the plaintext we are now able to work only on the cipher toast a last issue that we know that we saw to the output sequence which saw the output of the first reducer so it means that we have when we try to break the register one by one we have to systematically include the first register which is part of the backdoor just to make things a little bit more complicated complicated that it says so in fact you just are going to attack register couple of register by Coppola receptor for register and retrieve the key to Koresh classical correction attack is not a problem so if you remember the key size 128 so normally

you could expect ready to do an exhaustive search 2 to the power 128 but in this case you have a Koopman an attack complexity which is ranging from 2 to the power 39 to 2 to the power 91 and you just need 6 kilobyte 6 kilobyte bit 6 kilo bits sorry of ciphertext so you always you can always add this amount of ciphertext no problem so here you have the summary of the different case so and remember I will speak at the end of the class so the biggest class about 60% of the keys you can break hit with a very strong correlation low complexity to to the poor so Tina it means that breaking a 60% of the cases

is easy to to supersalty 9 is nowadays very easy and you have the other classes and of course this class in this class C's 3 and 3/4 are becomes difficult even nowadays being able to break 2 to the power 91 is still difficult I don't say I don't know whether the NSA or a Chinese eyeball but still consider as very difficult to reach not to say impossible but until here it is considered to be tractable so you have a general description of the attacker rhythm he just for one given register and of course you apply it to the different register you want to you want Ricky to be referred of course it is abdicating you just keep the best score

but if you want to do soft decoding you say okay I will for example keep I would say ten or twenty or fifty or hundred best keys based on today and then to fill a it's very easy and it is not very time-consuming so you can of relax your decision and optimize your probability of success so now we have seen that in fact this algorithm contrary to the to the appearances is weak but from a general point of view it seems to be strong now how to you that remember that more and more were speaking about control of cryptography for example let us take the case of NATO NATO you have 27 countries and as far as I know until late a nine

90s early 2000 in fact all the encryption algorithm used by the Aryans were provided by the USA USA as well as the keys it was for interrupting interoperability issues and of course security remember control of come to work until late 90s the different countries of the Alliance had no access to the encryption algorithm description the problem is okay you provide a very strong algorithm for your military needs but one controller to say Portugal of France decide maybe to use this algorithm in less control way across Italy when you give crypto you give a weapon remember the Vasa Narwhal so how to manage this are to make sure that even you don't play the rules that you will

be still able to control it is what I call the strong key with these crypto systems in fact depending on the class of the key you you are the algorithm will be more or less strong just imagine in more than all contact for example ice P provider whatever you want that a client decide not to follow the words and to use their the provided algorithm in a different way that phrasing 0 condition of huge specified space 5 we want to respect those so the basic idea behind this kind of algorithm which say ok is going to use the the client is going to use is a letís but with I probability the keys will weaken

the algorithm so I will be able to write the algorithm not less in the case of BSA true in fact you see that 60% of the trees will fall in the c0 class it means that you will be able to break 60% of the traffic with the complexity around 2 to the power 39 and if you want to provide strong security when you when the client play the game play the game and respect the rules in fact keys are provided by from the c-4 class the most difficult class to break of course you have a lot of possible scenario to imagine it is just a general scheme just to make you aware of this kind of subtleties so auto-tuned

in fact and all the news I am going to show you comes from the 10 last days the VI recurrently one to one that the IT industry implement backdoors in encryption its nightmare is end-to-end encryption this is Department from the US but also from the European you and community tries irregularly speak about well let us enforce back doors and try to push laws in order to enable this weakening mechanism so it's very concerning because we cannot on one side as to protect the industry to protect to protect a citizen and to enable them to be protected and on the other side to say okay trust us we are going to control everything and it's not possible to so

more recently it was a few days ago they decide we are of course a lot of good argument to protection run or take everything we want but in fact they want to weaken the encrypted security and of course you have a sub G escrowing so you are able to use your crypto but you have to give to give me your key for example Microsoft as you you can include but you have to provide to accept the escrow mean or the other solution is back though that's so the last interval in Europe and in work a police organization we are a strong which is striding also to input back tones so I am convinced we need a lot of research in this area it's

very important to prove that it is probable and to be aware of the fact that more and more this issue will be wearing issue I don't think it's this argument to protect yourself by weakening crypto is a good argument it is a fast a wrong argument so of course our lot of work to do so for example were working on different crypto committee for stream ciphers nonlinear feedback shift register or using memory on apology Brutus algorithm is a stream cipher with easy row with memory memory bits and we are going to try to extend the idea of wiki strong key cryptosystem to block ciphers working at the key scheduling algorithm sonali by mid-january all the

technical details and the complete description of the algorithm to attack the stream cipher will be available so thank you very much it's having a question

yes but what the second we have a question over there thank you for your talk quick question that you mention about how not using a closed source cryptography and how open source cryptography is better and some advantages but I'm remembering so I want to ask about France is France nowadays more defending that posture and be against key regulation or key scheduling a bad one like because in practice like sharing your key schedules is not a good idea because you know in the 90s France would forbid strong SSL and so on and so as how as your opinion because you know the context has been shipped in that mentality or is that still that mentality oh we load the key we load the

cipher we don't think about it anymore no you write the position of France was always well strange first just to remember until 2004 the cryptography was limited to 64-bit not to say I think even 40 which was of course totally stupid I'm from France but I was among I was matteri at the time as I know it's totally stupid it's not possible but even in France and the former interim Minister organic as nerve we stopped at the major in Germany tried as well to say we have to break to input backdoors it is totally stupid because bad guys the most better the baddest guy are not using cryptography if you see our Italian mafia is working they don't use

smartphone and so on so breaking cryptography which really is not a solution there is a strong need for citizens for industry to protect the traffic now I convey that we must add a fully open cryptography but it is a necessary condition it comes from the 19th slow from kak off that say we must know the algorithm the security must not rely on the secret of our algorithm only of the scatter of the key but the aim of this research it to say ok necessary condition not a sufficient one but you're right I'm very concerning and concerned about the France is the country who wrote the the right of human as a human right so I

think we have a moral responsibility to defend strong cryptography but it's true that in Europe and in France is a very easy solution for police forces easily ok we are not very strong so you will make sure that the citizen will be weak well it's a very strange position but you're right and we are to be very careful very cautious and to monitor the monitor any more question in your strong key wiki scenario how can the provider test which keys are strong and which are weak and how can't like in your example the countries that were using that crypto do the same thing to tell apart which keys are weak and which ones are strong in fact when you design your if

you intend to design such a shame social scheme sorry in fact you will of course may the prior analysis in order to be able to to identify and select the key which in this scenario we suppose form NATO so the United States but the provider we'll add this either knowledge of course it is everything is prepared and define specified during the algorithm design and test I believe hello thanks for your talk I have a question regarding for example SSH keys in the beginning you talk about elliptic curves so my question is regarding that so when we are creating a keeper for SSH for example what's your advice should we use elliptic curve keys or RSA keys what's

your opinion on that so it's strong debate in fact all girl algorithm are good in the case of the ECC RPG which is a random generator based on elliptic curves the problem was not elected curves it was the choice of some constant some particular value when those value has been chosen as a standard remember it was the ISO and NIST standard some cryptographic researchers say oh we are not trusted that those concerns very much but no one wanted to hear them in 2014 if I remember Snowden say ok the NSA paid 10 million dollars in order to make sure that the week constant will be chosen so once again it is not a race is probably

weak if if you consider quant the quantum computers but from a mathematical point of view with good parameters or req typical cryptography the very good algorithm but what is important to evaluate the different parameters so I would say let's tres open research the open crypto community they are very very active and trying to detect any attempt to modify or to weaken but once again mathematics is a very difficult area so we have everything must be open and I think it is very necessary to have a very huge open and lively research but once again I would not say one is better than the other it depends on your operational constraint for example a thicker product provides with a quite

same level of security smaller keys so for implementation of traffic purpose is better than RSA where you have very long keys okay thanks any more question [Music] No thank you Eric for your talk we will proceed