Browse Prior Art Database

Method for Detection/Rejection of Weak and Semi-weak Data Encryption Algorithm Keys Produced via a Key Generator

IP.com Disclosure Number: IPCOM000108948D
Original Publication Date: 1992-Jul-01
Included in the Prior Art Database: 2005-Mar-23
Document File: 5 page(s) / 164K

Publishing Venue

IBM

Related People

Abraham, D: AUTHOR [+6]

Abstract

This article describes two methods for the detection/rejection of weak and semi-weak keys produced by a data encryption algorithm (DEA) key generator. Since there are only 4 weak and 12 semi-weak DEA keys, the obvious method is to store the 16 64-bit patterns in a table and reject keys based on direct comparisons with a generated key. However, in some implementations, it may be inconvenient or uneconomical to store the necessary 16 x 64 = 1024 bits. Therefore, the described methods offer an alternative time/memory trade-off where detection/rejection is based on a fast calculation that tests for patterns in the generated key. A discovered pattern causes the key to be rejected. If no such pattern is found, the key is guaranteed not to be weak or semi-weak.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 50% of the total text.

Method for Detection/Rejection of Weak and Semi-weak Data Encryption Algorithm Keys Produced via a Key Generator

       This article describes two methods for the
detection/rejection of weak and semi-weak keys produced by a data
encryption algorithm (DEA) key generator.  Since there are only 4
weak and 12 semi-weak DEA keys, the obvious method is to store the 16
64-bit patterns in a table and reject keys based on direct
comparisons with a generated key.  However, in some implementations,
it may be inconvenient or uneconomical to store the necessary 16 x 64
= 1024 bits. Therefore, the described methods offer an alternative
time/memory trade-off where detection/rejection is based on a fast
calculation that tests for patterns in the generated key.  A
discovered pattern causes the key to be rejected.  If no such pattern
is found, the key is guaranteed not to be weak or semi-weak.
Cryptographically speaking, the algorithms are such that the number
of rejected keys causes only a very small reduction in the total key
space and, therefore, represents no real weakening of key security.

      Fig. 1 illustrates a cryptographic system consisting of a
cryptographic facility (CF) 1 capable of executing a set of
cryptographic instructions 2, key storage 3, a cryptographic facility
access program (CFAP) 4 with a weak/semi-weak DEA key filter routine
6, and an application program 5.  The KEYGEN instruction, located in
the CF at 2, generates random 64-bit DEA keys.  The steps involved in
generating a key via the KEYGEN instruction can be traced.
Typically, an application program first issues a create key request
to CFAP, which results in a KEYGEN instruction being issued to the
CF.  In response, the KEYGEN instruction generates a 64-bit random
number representing the requested candidate key, adjusts each byte
for odd parity, and returns the candidate key to CFAP.  CFAP then
tests the candidate key, via the weak/semi-weak key filter, to ensure
that it is neither weak nor semiweak.  If the candidate key is weak
or semi-weak, the KEYGEN instruction is again invoked and a new
candidate key obtained.  If the candidate key is not weak or
semi-weak, it is returned to the application.

      In an alternative implementation (not shown), the
weak/semi-weak DEA key filter can be located in the CF.  In that
case, candidate keys are both generated and tested within the CF.  In
situations where one must provide encrypted keys to CFAP, there is no
choice except to locate the weak/semi-weak DEA key filter within the
CF.  The example cited here illustrates an application involving
generation of clear keys, and assumes that the cryptographic system
is first placed in a secure state (e.g., quiesced and purged of other
active application programs).

      Fig. 2 contains a list of the four weak and 12 semi-weak DEA
keys.  Weak DEA keys have the property that there is no difference
between the results of encipherment and decipherment (i.e., two
s...