Differential cryptanalysis of Mod-2/Mod-3 constructions of binary weak PRFs
(2023) 2023 International Symposium on Information Theory p.477-482- Abstract
- Pseudo-random functions are a fundamental building block in many cryptographic applications. In certain scenarios, a weaker notion (where security is restricted to uniformly random input), but more computationally efficient, called weak pseudo-random functions, is sufficient. In this work, we present new differential attacks on the main binary weak pseudo-random function constructions, namely the so-called Alternative Mod-2/Mod-3. For the Alternative Mod-2/Mod-3 wPRF, the best distinguisher proposed by Cheon et al. achieves O(2 0.21n ) complexity, where n is the input length. We show that our attack asymptotically outperforms this and requires far fewer samples that can be applied in restricted oracle settings. By minimizing computational... (More)
- Pseudo-random functions are a fundamental building block in many cryptographic applications. In certain scenarios, a weaker notion (where security is restricted to uniformly random input), but more computationally efficient, called weak pseudo-random functions, is sufficient. In this work, we present new differential attacks on the main binary weak pseudo-random function constructions, namely the so-called Alternative Mod-2/Mod-3. For the Alternative Mod-2/Mod-3 wPRF, the best distinguisher proposed by Cheon et al. achieves O(2 0.21n ) complexity, where n is the input length. We show that our attack asymptotically outperforms this and requires far fewer samples that can be applied in restricted oracle settings. By minimizing computational complexity, we can achieve O(2 0.166n ) complexity. Additionally, in a small experiment, we indicate that their proposed fix of using keys with large Hamming weight is even more vulnerable to our attack. (Less)
Please use this url to cite or link to this publication:
https://lup.lub.lu.se/record/d00ee393-de9e-4390-b356-1eddea7da436
- author
- Johansson, Thomas LU ; Meier, Willi and Nguyen, Vu LU
- organization
- publishing date
- 2023
- type
- Chapter in Book/Report/Conference proceeding
- publication status
- published
- subject
- host publication
- 2023 IEEE International Symposium on Information Theory (ISIT),
- pages
- 477 - 482
- publisher
- IEEE - Institute of Electrical and Electronics Engineers Inc.
- conference name
- 2023 International Symposium on Information Theory
- conference location
- Taipei, Taiwan
- conference dates
- 2023-06-25 - 2023-06-30
- external identifiers
-
- scopus:85171474016
- ISBN
- 9781665475556
- 9781665475549
- DOI
- 10.1109/ISIT54713.2023.10206853
- language
- Swedish
- LU publication?
- yes
- id
- d00ee393-de9e-4390-b356-1eddea7da436
- date added to LUP
- 2023-10-04 15:13:07
- date last changed
- 2024-04-19 01:57:56
@inproceedings{d00ee393-de9e-4390-b356-1eddea7da436, abstract = {{Pseudo-random functions are a fundamental building block in many cryptographic applications. In certain scenarios, a weaker notion (where security is restricted to uniformly random input), but more computationally efficient, called weak pseudo-random functions, is sufficient. In this work, we present new differential attacks on the main binary weak pseudo-random function constructions, namely the so-called Alternative Mod-2/Mod-3. For the Alternative Mod-2/Mod-3 wPRF, the best distinguisher proposed by Cheon et al. achieves O(2 0.21n ) complexity, where n is the input length. We show that our attack asymptotically outperforms this and requires far fewer samples that can be applied in restricted oracle settings. By minimizing computational complexity, we can achieve O(2 0.166n ) complexity. Additionally, in a small experiment, we indicate that their proposed fix of using keys with large Hamming weight is even more vulnerable to our attack.}}, author = {{Johansson, Thomas and Meier, Willi and Nguyen, Vu}}, booktitle = {{2023 IEEE International Symposium on Information Theory (ISIT),}}, isbn = {{9781665475556}}, language = {{swe}}, pages = {{477--482}}, publisher = {{IEEE - Institute of Electrical and Electronics Engineers Inc.}}, title = {{Differential cryptanalysis of Mod-2/Mod-3 constructions of binary weak PRFs}}, url = {{http://dx.doi.org/10.1109/ISIT54713.2023.10206853}}, doi = {{10.1109/ISIT54713.2023.10206853}}, year = {{2023}}, }