Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Differential cryptanalysis of Mod-2/Mod-3 constructions of binary weak PRFs

Johansson, Thomas LU orcid ; Meier, Willi and Nguyen, Vu LU orcid (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:
author
; and
organization
publishing date
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}},
}