[논문]Algebraic Fault Analysis of UOV and Rainbow With the Leakage of Random Vinegar Values

Shim, Kyung-Ah; Koo, Namhun

doi:10.1109/tifs.2020.2969555

[해외논문] Algebraic Fault Analysis of UOV and Rainbow With the Leakage of Random Vinegar Values

IEEE transactions on information forensics and security, v.15, 2020년, pp.2429 - 2439

Shim, Kyung-Ah (Division of Basic Researches for Industrial Mathematics, National Institute for Mathematical Sciences, Daejeon, South Korea) , Koo, Namhun (Applied Algebra and Optimization Research Center, Sungkyunkwan University, Suwon, South Korea)

Abstract ▼ AI-Helper

A public-key cryptographic algorithm based on multivariate quadratic equations is one of promising post-quantum alternatives for current public-key cryptography. The security of multivariate quadratic schemes has been sufficiently analyzed mathematically, but few works have been devoted to implementation attacks. In this paper, we present algebraic fault analysis of two well-known multivariate quadratic schemes, UOV and Rainbow, which combines fault attacks with key recovery attacks using good keys. We focus on fault attacks which cause faults on random Vinegar values used in signing. Our fault models are divided into three cases according to the leakage types of the Vinegar values: reused, revealed and set to zero. We show that the equivalent key of UOV is completely recovered in polynomial time from $(m+1)$, $n$ and $m$ signatures generated by the entire faulty Vinegar values in the three cases, respectively. Specifically, the equivalent key of UOV is completely recovered from 45, 103 and 44 signatures generated by 59 bytes of faulty Vinegar values in the three cases, respectively, at a 128-bit security level. The equivalent key of Rainbow is also recovered from 44, 79 and 43 signatures with 36 bytes of faulty Vinegar values in the three cases, respectively. This is the first result that leads to the full secret key recovery of UOV and Rainbow from the leakage of the Vinegar values. In the other cases, we show that complexities of the key recovery attacks on Rainbow and UOV are significantly weakened in terms of the number of faulty Vinegar values. Our attacks can be applied to Rainbow and LUOV selected to NIST Post-Quantum Cryptography Standardization Round 2. Countermeasures against our attacks are investigated.

참고문헌 (36)

10.1007/0-387-34805-0_22
10.1007/978-3-030-16350-1_13
10.1109/FDTC.2014.17
Post-Quantum Cryptography Round 2 Submissions 2018
Wolf, C., Preneel, B.. Large Superfluous Keys in Multivariate Quadratic Asymmetric Systems. Lecture notes in computer science, vol.3386, 275-287.

상세보기
About the security of multivariate quadratic public key schemes thomae 2013
IACR Transactions on Cryptographic Hardware and Embedded Systems New Bleichenbacher records: Fault attacks on qDSA signatures takahashi 2018 10.46586/tches.v2018.i3.331-371 2018 331
Ding, J., Schmidt, D.. Rainbow, a New Multivariable Polynomial Signature Scheme. Lecture notes in computer science, vol.3531, 164-175.

상세보기
Ducas, L., Durmus, A., Lepoint, T., Lyubashevsky, V.. Lattice Signatures and Bimodal Gaussians. Lecture notes in computer science, vol.8042, 40-56.

상세보기
IACR Transactions on Cryptographic Hardware and Embedded Systems CRYSTALS-Dilithium: A lattice-based digital signature scheme ducas 2018 10.46586/tches.v2018.i1.238-268 2018 238
Android random number flaw implicated in Bitcoin thefts ducklin 2013
Espitau, Thomas, Fouque, Pierre-Alain, Gérard, Benoît, Tibouchi, Mehdi. Loop-Abort Faults on Lattice-Based Signature Schemes and Key Exchange Protocols. IEEE transactions on computers, vol.67, no.11, 1535-1549.

상세보기
10.1007/3-540-47721-7_12
Guneysu, T., Lyubashevsky, V., Poppelmann, T.. Practical Lattice-Based Cryptography: A Signature Scheme for Embedded Systems. Lecture notes in computer science, vol.7428, 530-547.

상세보기
Hashimoto, Y., Takagi, T., Sakurai, K.. General Fault Attacks on Multivariate Public Key Cryptosystems. Lecture notes in computer science, vol.7071, 1-18.

상세보기
Hoffstein, J., Pipher, J., Schanck, J.M., Silverman, J.H., Whyte, W.. Practical Signatures from the Partial Fourier Recovery Problem. Lecture notes in computer science, vol.8479, 476-493.

상세보기
Howgrave-Graham, N. A.; Smart, N. P. etc. "Lattice Attacks on Digital Signature Schemes." Designs, codes, and cryptography, v.23 no.3 (2001), pp. 283-290, doi:10.1023/A:1011214926272.
10.1007/978-3-662-48797-6_14
Experiments With DSA bleichenbacher 2005
Patarin, J., Courtois, N., Goubin, L.. QUARTZ, 128-Bit Long Digital Signatures. Lecture notes in computer science, vol.2020, 282-297.

상세보기
10.1109/FDTC.2016.11
IACR Transactions on Cryptographic Hardware and Embedded Systems Differential fault attacks on deterministic lattice signatures bruinderink 2018 10.46586/tches.v2018.i3.21-43 2018 21
Post-Quantum Cryptography Round 1 Submissions 2018
Bogdanov, A., Eisenbarth, T., Rupp, A., Wolf, C.. Time-Area Optimized Public-Key Engines: MQ-Cryptosystems as Replacement for Elliptic Curves?. Lecture notes in computer science, vol.5154, 45-61.

상세보기
Chen, A.I.-T., Chen, M.-S., Chen, T.-R., Cheng, C.-M., Ding, J., Kuo, E.L.-H., Lee, F.Y.-S., Yang, B.-Y.. SSE Implementation of Multivariate PKCs on Modern x86 CPUs. Lecture notes in computer science, vol.5747, 33-48.

상세보기
Proc 27th Chaos Commun Congr Console hacking 2010-ps3 epic fail hotz 2010
Bettale, Luk, Faugère, Jean-Charles, Perret, Ludovic. Hybrid approach for solving multivariate systems over finite fields. Journal of mathematical cryptology, vol.3, no.3,

상세보기
Czypek, P., Heyse, S., Thomae, E.. Efficient Implementations of MQPKS on Constrained Devices. Lecture notes in computer science, vol.7428, 374-389.

상세보기
10.1007/978-3-319-31517-1_3
Kipnis, A., Patarin, J., Goubin, L.. Unbalanced Oil and Vinegar Signature Schemes. Lecture notes in computer science, vol.1592, 206-222.

상세보기
10.1007/3-540-45961-8_39
10.1007/978-3-030-16350-1_11
Naccache, D., Nguyen, P. Q., Tunstall, M., Whelan, C.. Experimenting with Faults, Lattices and the DSA. Lecture notes in computer science, vol.3386, 16-28.

상세보기
De Mulder, Elke, Hutter, Michael, Marson, Mark E., Pearson, Peter. Using Bleichenbacher’s solution to the hidden number problem to attack nonce leaks in 384-bit ECDSA: extended version. Journal of cryptographic engineering, vol.4, no.1, 33-45.

상세보기
Nguyen, Phong Q.; Shparlinski, Igor E. etc. "The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces." Designs, codes, and cryptography, v.30 no.2 (2003), pp. 201-217, doi:10.1023/A:1025436905711.
Nguyen,, Shparlinski,. The Insecurity of the Digital Signature Algorithm with Partially Known Nonces. Journal of cryptology : the journal of the International Association for Cryptologic Research, vol.15, no.3, 151-176.

상세보기

LOADING...

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

원문 URL 링크

DOI : 10.1109/TIFS.2020.2969555
IEEE : 저널 > 논문

*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.

저작권 관리 안내

내보내기 메뉴

내보내기 구분

파일저장
인쇄
메일전송

구성항목

기본정보
상세정보

관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관

저장형식

Text(ASCII format)
Excel format
RefWorks Direct Export
RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley

메일정보

받는사람 (필수): @
보내는사람 (선택): @
제목
내용: KISTI 검색결과 이메일 서비스

안내

총 건의 자료가 검색되었습니다.

다운받으실 자료의 인덱스를 입력하세요. (1-10,000)

검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다.

데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요)

다운로드 파일은 UTF-8 형태로 저장됩니다.
파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오.

Text(ASCII format)
Excel format

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

AI-Helper ※ AI-Helper는 을 사용합니다.

AI-Helper

안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

연합인증