How secure is Skipjack?? (Skipjack.c algorithm included)

Networking/Security Forums -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security

Author: Agentsmith15Location: Texas... PostPosted: Sun Jul 25, 2004 5:50 am    Post subject: How secure is Skipjack?? (Skipjack.c algorithm included)
    ----
How secure is the skipjack Algorithm???

Code:
24 June 1998

----------------------------------------------------------------------
/*
  Skipjack, as defined in the document "Skipjack and KEA Algorithm
  dated 29 May 1998, and located at
   http://csrc.nist.gov/encryption/skipjack-1.pdf
   http://csrc.nist.gov/encryption/skipjack-2.pdf
  Note that there is no author, copyright, or other attribution on the
  PDF file.
  This implementation seems to successfully fit the test vectors
  listed in the documents. In fact, this version of the code simply
  prints the test vector out.
  The code is not optimized at all. It is written to be obvious, not
  necessarily to be fast.
  This code is hereby placed in the public domain. I would _like_ it
  if you gave me some credit, but you are under no obligation to do
  so.
  Perry E. Metzger, Piermont Information Systems Inc., 24 June 1998
  You can reach me via email at perry@piermont.com
*/

#include <stdio.h>#include <sys/types.h>
#define PRINTDUMP
/* #define TIMING */

typedef u_int8_t byte;
typedef u_int16_t word;

byte key[10];

const byte ftable[256] = {
/*         x0    x1    x2    x3    x4    x5    x6    x7    x8    x9    xA    xB    xC    xD    xE    xF*/
/* 0x */ 0xa3, 0xd7, 0x09, 0x83, 0xf8, 0x48, 0xf6, 0xf4, 0xb3, 0x21, 0x15, 0x78, 0x99, 0xb1, 0xaf, 0xf9,
/* 1x */ 0xe7, 0x2d, 0x4d, 0x8a, 0xce, 0x4c, 0xca, 0x2e, 0x52, 0x95, 0xd9, 0x1e, 0x4e, 0x38, 0x44, 0x28,
/* 2x */ 0x0a, 0xdf, 0x02, 0xa0, 0x17, 0xf1, 0x60, 0x68, 0x12, 0xb7, 0x7a, 0xc3, 0xe9, 0xfa, 0x3d, 0x53,
/* 3x */ 0x96, 0x84, 0x6b, 0xba, 0xf2, 0x63, 0x9a, 0x19, 0x7c, 0xae, 0xe5, 0xf5, 0xf7, 0x16, 0x6a, 0xa2,
/* 4x */ 0x39, 0xb6, 0x7b, 0x0f, 0xc1, 0x93, 0x81, 0x1b, 0xee, 0xb4, 0x1a, 0xea, 0xd0, 0x91, 0x2f, 0xb8,
/* 5x */ 0x55, 0xb9, 0xda, 0x85, 0x3f, 0x41, 0xbf, 0xe0, 0x5a, 0x58, 0x80, 0x5f, 0x66, 0x0b, 0xd8, 0x90,
/* 6x */ 0x35, 0xd5, 0xc0, 0xa7, 0x33, 0x06, 0x65, 0x69, 0x45, 0x00, 0x94, 0x56, 0x6d, 0x98, 0x9b, 0x76,
/* 7x */ 0x97, 0xfc, 0xb2, 0xc2, 0xb0, 0xfe, 0xdb, 0x20, 0xe1, 0xeb, 0xd6, 0xe4, 0xdd, 0x47, 0x4a, 0x1d,
/* 8x */ 0x42, 0xed, 0x9e, 0x6e, 0x49, 0x3c, 0xcd, 0x43, 0x27, 0xd2, 0x07, 0xd4, 0xde, 0xc7, 0x67, 0x18,
/* 9x */ 0x89, 0xcb, 0x30, 0x1f, 0x8d, 0xc6, 0x8f, 0xaa, 0xc8, 0x74, 0xdc, 0xc9, 0x5d, 0x5c, 0x31, 0xa4,

/* Ax */ 0x70, 0x88, 0x61, 0x2c, 0x9f, 0x0d, 0x2b, 0x87, 0x50, 0x82, 0x54, 0x64, 0x26, 0x7d, 0x03, 0x40,
/* Bx */ 0x34, 0x4b, 0x1c, 0x73, 0xd1, 0xc4, 0xfd, 0x3b, 0xcc, 0xfb, 0x7f, 0xab, 0xe6, 0x3e, 0x5b, 0xa5,
/* Cx */ 0xad, 0x04, 0x23, 0x9c, 0x14, 0x51, 0x22, 0xf0, 0x29, 0x79, 0x71, 0x7e, 0xff, 0x8c, 0x0e, 0xe2,
/* Dx */ 0x0c, 0xef, 0xbc, 0x72, 0x75, 0x6f, 0x37, 0xa1, 0xec, 0xd3, 0x8e, 0x62, 0x8b, 0x86, 0x10, 0xe8,
/* Ex */ 0x08, 0x77, 0x11, 0xbe, 0x92, 0x4f, 0x24, 0xc5, 0x32, 0x36, 0x9d, 0xcf, 0xf3, 0xa6, 0xbb, 0xac,
/* Fx */ 0x5e, 0x6c, 0xa9, 0x13, 0x57, 0x25, 0xb5, 0xe3, 0xbd, 0xa8, 0x3a, 0x01, 0x05, 0x59, 0x2a, 0x46
};


#define HIGH(x)      (((x) >> 8) & 0xff)
#define LOW(x)       ((x) & 0xff)
#define CONCAT(h, l) ((((word)(h)) << 8) | ((word)(l)))

#define CV(x) (key[((x) % 10)])

#define f(x) (ftable[(x)])

static word g(int k, word w)
{
   byte g1, g2, g3, g4, g5, g6;
   word ret;

   g1 = HIGH(w);
   g2 = LOW(w);

   g3 = f(g2 ^ CV(4*k  )) ^ g1;
   g4 = f(g3 ^ CV(4*k+1)) ^ g2;
   g5 = f(g4 ^ CV(4*k+2)) ^ g3;
   g6 = f(g5 ^ CV(4*k+3)) ^ g4;

   ret = CONCAT(g5, g6);

   return(ret);
}

static word inv_g(int k, word w)
{
   byte g1, g2, g3, g4, g5, g6;
   word ret;

   g6 = LOW(w);
   g5 = HIGH(w);
   g4 = f(g5 ^ CV(4*k+3)) ^ g6;
   g3 = f(g4 ^ CV(4*k+2)) ^ g5;
   g2 = f(g3 ^ CV(4*k+1)) ^ g4;
   g1 = f(g2 ^ CV(4*k  )) ^ g3;

   ret = CONCAT(g1, g2);
   return(ret);
}

static void dump(int i, word w1, word w2, word w3, word w4)
{
   printf("round %2d: %4.4x %4.4x %4.4x %4.4x\n", i, w1, w2, w3, w4);
}

static void ruleA(word *w1, word *w2, word *w3, word *w4, int k)
{
   word c, t1, t2, t3, t4, tmp;

   c = k + 1;
   
   t1 = *w1;
   t2 = *w2;
   t3 = *w3;
   t4 = *w4;

   tmp = g(k, t1);
   *w1 = tmp ^ t4 ^ c;
   *w2 = tmp;
   *w3 = t2;
   *w4 = t3;
}

static void ruleB(word *w1, word *w2, word *w3, word *w4, int k)
{
   word c, t1, t2, t3, t4;

   c = k + 1;
   
   t1 = *w1;
   t2 = *w2;
   t3 = *w3;
   t4 = *w4;

   *w1 = t4;
   *w2 = g(k, t1);
   *w3 = t1 ^ t2 ^ c;
   *w4 = t3;
}

static void inv_ruleA(word *w1, word *w2, word *w3, word *w4, int k)
{
   word c, t1, t2, t3, t4;

   c = k;
   
   t1 = *w1;
   t2 = *w2;
   t3 = *w3;
   t4 = *w4;

   *w1 = inv_g((k-1), t2);
   *w2 = t3;
   *w3 = t4;
   *w4 = t1 ^ t2 ^ c;
}

static void inv_ruleB(word *w1, word *w2, word *w3, word *w4, int k)
{
   word c, t1, t2, t3, t4, tmp;

   c = k;
   
   t1 = *w1;
   t2 = *w2;
   t3 = *w3;
   t4 = *w4;

   tmp = inv_g((k-1), t2);
   *w1 = tmp;
   *w2 = tmp ^ t3 ^ c;
   *w3 = t4;
   *w4 = t1;
}

void encrypt(word *w1, word *w2, word *w3, word *w4)
{
   int i, k;

   k = 0;

   for (i = 0; i < 8; i++) {
#ifdef PRINTDUMP
      dump(k, *w1, *w2, *w3, *w4);
#endif
      ruleA(w1, w2, w3, w4, k++);
   }

   for (i = 0; i < 8; i++) {
#ifdef PRINTDUMP
      dump(k, *w1, *w2, *w3, *w4);
#endif
      ruleB(w1, w2, w3, w4, k++);
   }
   
   for (i = 0; i < 8; i++) {
#ifdef PRINTDUMP
      dump(k, *w1, *w2, *w3, *w4);
#endif
      ruleA(w1, w2, w3, w4, k++);
   }
   
   for (i = 0; i < 8; i++) {
#ifdef PRINTDUMP
      dump(k, *w1, *w2, *w3, *w4);
#endif
      ruleB(w1, w2, w3, w4, k++);
   }
      
}

void decrypt(word *w1, word *w2, word *w3, word *w4)
{
   int i, k;

   k = 32;

   for (i = 0; i < 8; i++) {
#ifdef PRINTDUMP
      dump(k, *w1, *w2, *w3, *w4);
#endif
      inv_ruleB(w1, w2, w3, w4, k--);
   }

   for (i = 0; i < 8; i++) {
#ifdef PRINTDUMP
      dump(k, *w1, *w2, *w3, *w4);
#endif
      inv_ruleA(w1, w2, w3, w4, k--);
   }

   for (i = 0; i < 8; i++) {
#ifdef PRINTDUMP
      dump(k, *w1, *w2, *w3, *w4);
#endif
      inv_ruleB(w1, w2, w3, w4, k--);
   }

   for (i = 0; i < 8; i++) {
#ifdef PRINTDUMP
      dump(k, *w1, *w2, *w3, *w4);
#endif
      inv_ruleA(w1, w2, w3, w4, k--);
   }

}

int main(int argc, char **argv)
{
   int i;
   word w1, w2, w3, w4;

   /* plaintext 33221100ddccbbaa */
   w1=0x3322;
   w2=0x1100;
   w3=0xddcc;
   w4=0xbbaa;

   /* key       00998877665544332211 */
   key[0] = 0x00;
   key[1] = 0x99;
   key[2] = 0x88;
   key[3] = 0x77;
   key[4] = 0x66;
   key[5] = 0x55;
   key[6] = 0x44;
   key[7] = 0x33;
   key[8] = 0x22;
   key[9] = 0x11;

#ifdef TIMING
   for (i = 0; i < 65536; i++)
#endif
      encrypt(&w1, &w2, &w3, &w4);

   dump(32, w1, w2, w3, w4);

#ifdef TIMING
   for (i = 0; i < 65536; i++)
#endif
      decrypt(&w1, &w2, &w3, &w4);

   dump(00, w1, w2, w3, w4);
}

Author: mjuarez PostPosted: Sun Jul 25, 2004 9:46 am    Post subject:
    ----
Type "Skipjack cryptanalysis" in a Google search. Or if you're feeling lazy, just click here:

http://www.google.com/search?sourceid=mozclient&ie=utf-8&oe=utf-8&q=skipjack+cryptanalysis

From this quick search, it appears that there are attacks proposed for 31 of the 32 rounds in Skipjack. Not a very good margin for security, if you ask me.

Marcos

Author: dataLocation: India PostPosted: Sun Jul 25, 2004 4:46 pm    Post subject:
    ----
hi,


Wasn't it skipjack, that was tainted by the NSA?

Data.

Author: mjuarez PostPosted: Sun Jul 25, 2004 8:54 pm    Post subject:
    ----
datah wrote:
Wasn't it skipjack, that was tainted by the NSA?


Er.... it was designed by the NSA. The design criteria were not released, but the complete algorithm was.

Marcos


Last edited by mjuarez on Mon Jul 26, 2004 8:41 am; edited 1 time in total

Author: JustinTLocation: Asheville, NC, US / Uberlāndia, MG, Brazil PostPosted: Mon Jul 26, 2004 1:02 am    Post subject: Skipjack.
    ----
If you consider the word "tainted" to be synonymous with the word "designed", I suppose so, but that isn't a fair assumption; the NSA designs good cryptography, when they wish to. The design of Skipjack itself can be implemented with or without escrowed encryption keys; that was just a particular application mandated by the NSA. The paranoia that seems to be inherent in the public's view of government-sanctioned cryptography stems from applications such as escrowed encryption standards. You shouldn't confused "design" with "application", because the former can exist within a myriad of the latter. I've spoken a little about this type of cryptography, here.

Overall, for Skipjack, I agree with Marcos - there is no good security margin with it. It isn't a very conservative design, as far as security goes, since it is susceptible, in reduced-round variation flavors (i.e., 3XOR, 4XOR, 16-round, 31-round, et cetera), to cryptanalytical attacks, both linear and differential; some of these attacks are more effective than brute force, such as an attacking using impossible differentials. It's not horribly broken, in its entirety, but it does remain in a fragile state of very minimal security. However, you may be surprised to hear that some cryptographers will still recommend it, for certain applications. It's actually a logical recommendation, when you disregard security. How, you may wonder?

Skipjack's savior is the indirect result of what we can gather about its design criteria. Although very little has ever been released about the design criteria of NSA-spawned cryptographic primitives, we do, however, know quite a bit about our criteria for designing a secure block cipher. When in juxtaposition with our criteria, Skipjack doesn't seem to be developed when many of these in mind, and tends to be rather hardware-implementation friendly. We notice a lot of instances in the execution of Skipjack that we don't notice in other block ciphers. The significance of this lies in the fact that many NSA-derived algorithms behave this way; they are efficient in hardware. Because of this efficiency and straightforward design, they are recommended as nice hardware implementations (i.e., 8-bit microcontrollers).

Perhaps this method of ruling out design criteria will aid in our analysis of the exact aim in design of these algorithms. Pinpointing tradeoffs can reveal a hefty amount of information. One observation I've made is the existence of a possible tradeoff between security and hardware efficiency. Take a look at military applications of classified algorithms, just to get a feel for how vital hardware efficiency is.

Skipjack was the first major revelation of what goes on behind the cryptographic doors of the NSA, as far as complete, conventional symmetric block ciphers go. Skipjack's first application was a mistake, because it was developed in a closed setting, and commercialized without any tremendous amount of public confidence. But even as this was a mistake, I believe the NSA is competent enough to have known the kind of security margin they expected it to achieve, in the first place. At the time of Skipjack's birth in the 1980s, differential cryptanalysis was known amongst the cryptographers and cryptanalysts at the NSA, which shows that they were a decade or two ahead of us, at that time. It's logical to assume that they weren't that worried about the disclosure of Skipjack. It's a 64-bit block ciphers utilizing an 80-bit key. Even at the most flawless effort, there is only so much security that can be achieved through these parameters. Other NSA-made designs, with far better parameters, exist, and have started to make their way to standard specification. If anything, it gave us an idea as to what kind of cryptography they can produce, and any insight to cryptanalysis, such as this, is a positive thing, even if it is just a flea compared to the gargantuan-secure designs the NSA is capable of rendering.

It has its appealing efficiencies, but it isn't packing a conservatively flexible margin of security. That's what it all boils down to. Either way, this was expected, at very little surprise. Because modern, conventional block ciphers are becoming more and more efficient for both software and hardware implementation, along with much more conservative designs, the reasons to recommend Skipjack above these others are quickly diminishing, in my opinion. Skipjack's margin of safety took a nice cryptanalytical malleting, of which it probably wasn't designed to defend against, totally, to begin with. If you do use it, use it because you have some need for its hardware efficiency; not because of its small margin of security. Even then, my personal recommendation would consist of other block ciphers, instead.

Author: dataLocation: India PostPosted: Tue Jul 27, 2004 3:24 pm    Post subject:
    ----
hi justin,

I have no doubt about the NSA's capabilities to design ciphers. Mostly worried that they can put a backdoor that will go undetected. No body knows why they changed DES, S-box values and till date there hasn't been much analysis on whether the changed S-boxes increased or decreased the susceptability to linear and differential attacks, except that a few reports suggest a few small weaknesses in the new s-boxes.

Data.

Author: Matt Crypto PostPosted: Tue Jul 27, 2004 9:51 pm    Post subject:
    ----
Hi datah; you say "nobody knows why they changed DES S-box values" -- actually, we've a pretty good idea that the S-boxes (and other components) were chosen to increase resistance against differential cryptanalysis (DC), because in 1994, one of the designers of DES, IBM's Don Coppersmith, released the previously undisclosed design criteria for DES. That IBM (and NSA) knew about DC had been suspected before Coppersmith's publication; Biham and Shamir showed that a number of seemingly minor changes to DES can weaken the cipher against DC. Because of this, people generally believe that any NSA involvement only increased security, and few now suspect a backdoor. (Have a look at http://en.wikipedia.org/wiki/DES for more info).

Author: JustinTLocation: Asheville, NC, US / Uberlāndia, MG, Brazil PostPosted: Wed Jul 28, 2004 1:31 am    Post subject: Actually, we do.
    ----
Correct. There isn't that much paranoia-ridden questioning, anymore, in regards to the security of the NSA-altered S-boxes. Analyses, by Biham and Shamir, did, in fact, demonstrate optimization towards the resilience of differential cryptanalysis - right down to the very order; on the other hand, this obvious optimization didn't exist, for linear cryptanalysis. The S-boxes of DES have undergone extensive, solid cryptanalytical scrutiny. Only the overly-conspiracy-theorist misinformed still refuse to let go of their "the NSA taints all cryptography" theories. There's logical reason to believe that the NSA had decently secure intentions in mind for this non-linear portion of DES. Differential cryptanalysis is older than linear cryptanalysis, and it's also obvious that the bulk of the DES design criteria centered around the former. Their knowledge of differential cryptanalysis becomes evident when you compare the S-boxes to their design criteria. You can't ever be certain that the NSA wouldn't do this, but cryptanalysis steers us towards a more comforting conclusion, in this case.

The fact is, the S-boxes of DES are fragile. As has already been mentioned, even minor alterations to their entries can result in devastating insecurity. There have been proposals for other, better S-boxes that are secure against both linear and differential cryptanalysis, but rest assured it was no trivial task. Changing the composition of an S-box is a meticulous venture, and a very dangerous one. You can't mindlessly choose them. DES came at a time when the private sector knew more than the public community, but also, when components were much less trivial to securely design because of the virgin field of modern cryptanalysis. Overall, with a few oppositions, I think the design criteria for DES was decently prepared. I doubt the NSA would even have had that significant of a reason to taint DES, anyhow; look at the insufficient key length - that's tainting enough. Because of this, it never had a huge margin of security; but, that's nothing new.

There are alternate configurations for DES-like variants, but Biham's variants, utilizing key-dependent S-boxes that were cryptographically-chosen for a more balanced, and robust, resilience to both linear and differential cryptanalysis, have since set a great example for designing DES-like ciphers with stout non-linear components. Triple-DES isn't the only surviving advantageous result of the DES era. Cryptographic-algorithm-wise, the NSA involvement has generally rendered security. It's most the scenarios in which the NSA has applied cryptography that have sparked controversy and ignited the paranoia of the community.

In this case, and contrary to some speculation, we do have an acceptable reasoning for what constituted the change and the primary cryptanalytical branch it was meant to addresses; there actually is quite a bit of published cryptanalysis on the core of this issue.

Author: dataLocation: India PostPosted: Wed Jul 28, 2004 9:43 am    Post subject:
    ----
hi,

thank you for the info, I think you are right about it. Because of the small key size, I saw a cypherpunks posting today saying ,that the FIPS standard for DES is being withdrawn and may only use triple des and preferably use rijandael(AES) for federal govt agencies securing data.

Data.



Networking/Security Forums -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security


output generated using printer-friendly topic mod, All times are GMT + 2 Hours

Page 1 of 1

Powered by phpBB 2.0.x © 2001 phpBB Group