Mathematical countermeasures against implementationattacks

Abstract

Baglantılı cihazların kullanımındaki hızlı geli¸smeler, güvenli ˘ gi sa ˘ glayan güçlü me- ˘totlara ihtiyaç dogurmu¸stur. Güvenilir bir iç dizayna sahip olan kara kutu modelinde, ˘güvenilir kriptografik algoritmaların kullanımı, kriptografik anahtar depolayan cihazları koruyor gibi görünür. Ancak, bu cihazların fiziksel kaçaklarının, anahtarın yada diger hassas bilgilerin sızmasına sebep oldu ˘ gu gösterilmi¸stir. Gri kutu denilen bu ˘model, algoritmanın kendisinden ziyade kriptografik algoritmanın donanımdaki gerçeklenmesine odaklanır. Bu fiziksel sızıntılar bir programın çalı¸sma süresi, harcadıgı˘güç ya da yaydıgı elektromanyetik radyasyon gibi yan-kanal bilgileri olabilir. Eger ˘bu sızıntı, cihaz içinde saklanan gizli bilginin tamamıyla veya bir parçasıyla iliskiliyse, yan-kanal bilgisi olarak adlandırılır. En ba¸sarılı ¸sekilde kullanılan yan-kanallar,diferansiyel güç analizi (DPA) ile çözümlenebilen kriptosisteminin güç tüketimidir.Güç tüketimini kullanan bir DPA saldırısının amacı, kriptografik sistemdeki farklı düzmetin ve anahtar giri¸slerinin farklı güç tüketiminin ölçümü ve analizleriyle, cihazdakianahtarı veya diger hassas bilgileri çıkarmaktır. Saldırgan, yan-kanaldan sızan bilgiler ˘ile kriptografik algoritmanın ara sonuçları arasında bir korelasyon bulmaya çalı¸sır.Son yirmi yılda saldırıların geni¸s çaplı etkisi nedeniyle, Yan-Kanal Analizi (SCA)saldırılarının önlenmesi büyük bir ara¸stırma konusu olmu¸stur ve bu saldırıları engellemek için birçok önlem geli¸stirilmi¸stir. Yeniden anahtarlama, aynı anahtarı kullanarak bir algoritmanın yineleme sayısını sınırlar; gizleme, herhangi bir hassas bilgidenixbagımsız olarak, her girdi için e¸sit miktarda güç tüketmesini sa ˘ glamak amacıyla algo- ˘ritmadan ziyade aygıtın davranı¸sını degi¸stirir; ve bizim çalı¸stı ˘ gımız tedbir olan mas- ˘keleme ise bir yan-kanaldan sızan bilgiler ile hassas veriler arasındaki ili¸skiyi önlerveya azaltır, ki SCA saldırıları da bu korelasyona baglıdır. Maskeleme, tüm hassas ˘ara degerleri, iyi bilinen gizli payla¸sım ¸semalarıyla rastgele hale getirerek gizler. Biri ˘E¸sik Gerçeklemesi (TI) [35] olan farklı maskeleme ¸semaları önerilmi¸stir. Küçük teknik problemlerin varlıgında bile DPA'ya kar¸sı güvenli oldu ˘ gu kanıtlanmı¸stır, aynı za- ˘manda diger güvenli maskeleme yöntemlerine kıyasla daha küçük bir alan gerektirir ˘ve çok daha az rastgelelik kullanır.TI, hassas verilerin her bir bitinin e¸sit olasılıkla payla¸sımlara ayrıldıgı gizli payla¸sım ˘ve çok partili hesaplamaya dayanır, böylece herhangi bir payla¸sım alt kümesi, verilerin kendisinden bagımsızdır. TI dört özelli ˘ ge, maskelenmemi¸s de ˘ gi¸skenlerin tekdüze- ˘ligine, do ˘ grulu ˘ ga, d. seviyeden tamsızlı ˘ ga ve payla¸sılan fonksiyonların tekdüzeli ˘ gine ˘dayanır. TI'nin ilk çalı¸smaları, TI'nin afin dönü¸süm altında degi¸smez oldu ˘ gunu gös- ˘termi¸stir.Bu tezin katkılarını iki bölümde sunuyoruz. ˙Ilk bölümde, S-kutularının dogrusal ol- ˘mayan bir dönü¸süm altında TI payla¸sımının davranı¸sını inceledik ve S-kutularınınbazı sınıfları haricinde TI'nin ters dönü¸süm altında degi¸smez olmadı ˘ gını gösterdik. ˘Tezin ikinci bölümünde, yüksek dereceli S-kutularını payla¸smanın etkili yöntemlerinden biri olan ayrı¸sma yöntemi çalı¸sılmı¸stır. Yüksek dereceli S-kutularının hangi¸sartlar altında daha dü¸sük dereceli olanlara ayrı¸stırılabilecegi incelendi. Bu ko¸sulları ˘bulmak için, güç permütasyonları ve pariteleri dikkate alınarak, permütasyonların kuadratik veya kübik permütasyonlara ayrılması hedeflenmi¸stir. Son olarak, sonlu cisimler ve bunlara kar¸sılık gelen dü¸sük dereceli güç permütasyonları hakkındaki ayrı¸smasonuçlarını sunuyoruz.

The rapid growth of the usage of connected devices demands strong methods to provide the security. In a black-box model with a trustworthy internal design, usage of secure cryptographic algorithms seems to protect the devices that stores a cryptographickey. However, the physical leakage of these devices has been shown to cause the extraction of the key or other sensitive information, in the so called gray-box model, focusing on the implementation of the cryptographic algorithms in hardware instead ofthe algorithms themselves. These physical leakages can be any side-channel information such as timing of an execution, power consumption or electromagnetic radiation.If the leakage is related to all or a part of the sensitive information stored in the device,it is called side-channel information. The most successfully exploited side-channelsis the power consumption of the cryptosystem which can be analyzed by differential power analysis (DPA). The aim of a DPA attack using the power consumptionis to extract the key or any other sensitive information from a device, through measurement and analysis of the different power consumption of different plaintext andkey inputs in the cryptographic system. The attacker seeks to find a correlation between the information leaked from the side-channel and the intermediate results of acryptographic algorithm.Due to the wide-ranging impact of the attacks over the last two decades, preventingSide-Channel Analysis (SCA) attacks has been the subject of a large body of research,and many countermeasures have been developed to foil these attacks. Rekeying limits the number of iterations of an algorithm using the same key, hiding changes thebehavior of a device rather than the algorithm to make it consume equal amount ofpower for any values of sensitive information, and masking, which we study, avoidsor reduce the correlation between information leaked through a side-channel and sensitive data, on which SCA attacks depends. Masking conceals all sensitive intermediate values by randomizing them with well-known secret sharing schemes. Differentmasking schemes have been proposed, one of which is Threshold Implementation(TI) [35]. It carries a proof of security against DPA even in the presence of glitches,while it requires smaller area and uses much less randomness compared to the othersecure masking methods.TI is based on secret sharing and multi-party computation in which each bit of thesensitive data is probabilistically divided into shares so that any proper subset ofshares is independent of the data itself. TI relies on four properties; uniformity ofthe unmasked variables, correctness, dth-order non-completeness and uniformity ofthe shared functions. The early works of TI provide the fact that TI is invariant underthe affine transformation.We present the contributions of this thesis in two-folds. In the first part, we examine the behavior of TI-sharing of S-boxes under a nonlinear transformation andwe showed TI is not invariant under inverse transformation except for a subset ofclasses. In the second part of the thesis, one of the efficient method to share higherdegree S-boxes which is the decomposition is studied. We examine when the S-boxesof higher degree can be decomposed into the lower degree ones. In order to findthe conditions, we target the decomposition of permutations into quadratic or cubicpermutations by considering the power permutations and their parities. We finallygive the decomposition results about the finite fields and corresponding lower degreepower permutations.