Institutional Research Information Service
UCL Logo
Please report any queries concerning the funding data grouped in the sections named "Externally Awarded" or "Internally Disbursed" (shown on the profile page) to your Research Finance Administrator. Your can find your Research Finance Administrator at https://www.ucl.ac.uk/finance/research/rs-contacts.php by entering your department
Please report any queries concerning the student data shown on the profile page to:

Email: portico-services@ucl.ac.uk

Help Desk: http://www.ucl.ac.uk/ras/portico/helpdesk
Publication Detail
Algebraic Attacks over GF(2^k), Cryptanalysis of HFE Challenge 2 and Sflash-v2
  • Publication Type:
  • Authors:
    Courtois NT
  • Publisher:
  • Publication date:
  • Place of publication:
    Berlin / Heidelberg, Germany
  • Pagination:
    201, 217
  • Published proceedings:
    Public Key Cryptography - PKC 2004: 7th International Workshop on Theory and Practice in Public Key Cryptography, Singapore, March 1-4, 2004: Proceedings
  • Volume:
  • Series:
    Lecture Notes in Computer Science
  • Editors:
    Bao F,Deng R,Zhou J
  • ISBN-10:
  • Status:
  • Language:
  • Keywords:
    XL Algorithms and Variants, Sflash signature scheme, HFE public key cryptosystem, Algebraic Cryptanalysis
The problem MQ of solving a system of multivariate quadratic equations over a finite field is relevant to the security of AES and for several public key cryptosystems. For example Sflash, the fastest known signature scheme (cf. [1]), is based on MQ equations over GF(27), and Patarin’s 500 $ HFE Challenge 2 is over GF(24). Similarly, the fastest alleged algebraic attack on AES due to Courtois, Pieprzyk, Murphy and Robshaw uses a MQ system over GF(28). At present very little is known about practical solvability of such systems of equations over GF(2 k ). The XL algorithm for Eurocrypt 2000 was initially studied over GF(p), and only recently in two papers presented at CT-RSA’02 and ICISC’02 the behaviour of XL is studied for systems of equations over GF(2). In this paper we show (as expected) that XL over GF(2 k ), k>1 (never studied so far) does not always work very well. The reason is the existence of additional roots to the system in the extension field, which is closely related to the remark made by Moh, claiming that the XSL attack on AES cannot work. However, we explain that, the specific set of equations proposed by Murphy and Robshaw already contains a structure that removes the problem. From this, we deduce a method to modify XL so that it works much better over GF(2 k ). In addition we show how to break the signature scheme Sflash-v2 recently selected by the European consortium Nessie, by three different methods derived from XL. Our fastest attack is in 258. All the three attacks apply also to HFE Challenge 2, and our best attack is in 263.
Publication data is maintained in RPS. Visit https://rps.ucl.ac.uk
 More search options
There are no UCL People associated with this publication
University College London - Gower Street - London - WC1E 6BT Tel:+44 (0)20 7679 2000

© UCL 1999–2011

Search by