Author: erodriguez
Date: Mon Apr 30 21:06:47 2007
New Revision: 533933
URL: http://svn.apache.org/viewvc?view=rev&rev=533933
Log:
An implementation of the n-fold algorithm, as required by RFC 3961, "Encryption and Checksum
Specifications for Kerberos 5."
o N-Fold implementation.
o Unit test verifying test vectors from RFC 3961.
Added:
directory/apacheds/branches/kerberos-encryption-types/kerberos-shared/src/main/java/org/apache/directory/server/kerberos/shared/crypto/encryption/NFold.java
(with props)
directory/apacheds/branches/kerberos-encryption-types/kerberos-shared/src/test/java/org/apache/directory/server/kerberos/shared/crypto/
directory/apacheds/branches/kerberos-encryption-types/kerberos-shared/src/test/java/org/apache/directory/server/kerberos/shared/crypto/encryption/
directory/apacheds/branches/kerberos-encryption-types/kerberos-shared/src/test/java/org/apache/directory/server/kerberos/shared/crypto/encryption/NFoldTest.java
(with props)
Added: directory/apacheds/branches/kerberos-encryption-types/kerberos-shared/src/main/java/org/apache/directory/server/kerberos/shared/crypto/encryption/NFold.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/kerberos-encryption-types/kerberos-shared/src/main/java/org/apache/directory/server/kerberos/shared/crypto/encryption/NFold.java?view=auto&rev=533933
==============================================================================
--- directory/apacheds/branches/kerberos-encryption-types/kerberos-shared/src/main/java/org/apache/directory/server/kerberos/shared/crypto/encryption/NFold.java
(added)
+++ directory/apacheds/branches/kerberos-encryption-types/kerberos-shared/src/main/java/org/apache/directory/server/kerberos/shared/crypto/encryption/NFold.java
Mon Apr 30 21:06:47 2007
@@ -0,0 +1,219 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.server.kerberos.shared.crypto.encryption;
+
+
+/**
+ * An implementation of the n-fold algorithm, as required by RFC 3961,
+ * "Encryption and Checksum Specifications for Kerberos 5."
+ *
+ * "To n-fold a number X, replicate the input value to a length that
+ * is the least common multiple of n and the length of X. Before
+ * each repetition, the input is rotated to the right by 13 bit
+ * positions. The successive n-bit chunks are added together using
+ * 1's-complement addition (that is, with end-around carry) to yield
+ * a n-bit result."
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class NFold
+{
+ /**
+ * N-fold the data n times.
+ *
+ * @param n The number of times to n-fold the data.
+ * @param data The data to n-fold.
+ * @return The n-folded data.
+ */
+ public static byte[] nFold( int n, byte[] data )
+ {
+ int k = data.length * 8;
+ int lcm = getLcm( n, k );
+ int replicate = lcm / k;
+ byte[] sumBytes = new byte[lcm / 8];
+
+ for ( int i = 0; i < replicate; i++ )
+ {
+ int rotation = 13 * i;
+
+ byte[] temp = rotateRight( data, data.length * 8, rotation );
+
+ for ( int j = 0; j < temp.length; j++ )
+ {
+ sumBytes[j + i * temp.length] = temp[j];
+ }
+ }
+
+ byte[] sum = new byte[n / 8];
+ byte[] nfold = new byte[n / 8];
+
+ for ( int m = 0; m < lcm / n; m++ )
+ {
+ for ( int o = 0; o < n / 8; o++ )
+ {
+ sum[o] = sumBytes[o + ( m * n / 8 )];
+ }
+
+ nfold = sum( nfold, sum, nfold.length * 8 );
+
+ }
+
+ return nfold;
+ }
+
+
+ /**
+ * For 2 numbers, return the least-common multiple.
+ *
+ * @param n1 The first number.
+ * @param n2 The second number.
+ * @return The least-common multiple.
+ */
+ protected static int getLcm( int n1, int n2 )
+ {
+ int temp;
+ int product;
+
+ product = n1 * n2;
+
+ do
+ {
+ if ( n1 < n2 )
+ {
+ temp = n1;
+ n1 = n2;
+ n2 = temp;
+ }
+ n1 = n1 % n2;
+ }
+ while ( n1 != 0 );
+
+ return product / n2;
+ }
+
+
+ /**
+ * Right-rotate the given byte array.
+ *
+ * @param in The byte array to right-rotate.
+ * @param len The length of the byte array to rotate.
+ * @param step The number of positions to rotate the byte array.
+ * @return The right-rotated byte array.
+ */
+ private static byte[] rotateRight( byte[] in, int len, int step )
+ {
+ int numOfBytes = ( len - 1 ) / 8 + 1;
+ byte[] out = new byte[numOfBytes];
+
+ for ( int i = 0; i < len; i++ )
+ {
+ int val = getBit( in, i );
+ setBit( out, ( i + step ) % len, val );
+ }
+ return out;
+ }
+
+
+ /**
+ * Perform one's complement addition (addition with end-around carry). Note
+ * that for purposes of n-folding, we do not actually complement the
+ * result of the addition.
+ *
+ * @param n1 The first number.
+ * @param n2 The second number.
+ * @param len The length of the byte arrays to sum.
+ * @return The sum with end-around carry.
+ */
+ protected static byte[] sum( byte[] n1, byte[] n2, int len )
+ {
+ int numOfBytes = ( len - 1 ) / 8 + 1;
+ byte[] out = new byte[numOfBytes];
+ int carry = 0;
+
+ for ( int i = len - 1; i > -1; i-- )
+ {
+ int n1b = getBit( n1, i );
+ int n2b = getBit( n2, i );
+
+ int sum = n1b + n2b + carry;
+
+ if ( sum == 0 || sum == 1 )
+ {
+ setBit( out, i, sum );
+ carry = 0;
+ }
+ else if ( sum == 2 )
+ {
+ carry = 1;
+ }
+ else if ( sum == 3 )
+ {
+ setBit( out, i, 1 );
+ carry = 1;
+ }
+ }
+
+ if ( carry == 1 )
+ {
+ byte[] carryArray = new byte[n1.length];
+ carryArray[carryArray.length - 1] = 1;
+ out = sum( out, carryArray, n1.length * 8 );
+ }
+
+ return out;
+ }
+
+
+ /**
+ * Get a bit from a byte array at a given position.
+ *
+ * @param data The data to get the bit from.
+ * @param pos The position to get the bit at.
+ * @return The value of the bit.
+ */
+ private static int getBit( byte[] data, int pos )
+ {
+ int posByte = pos / 8;
+ int posBit = pos % 8;
+
+ byte valByte = data[posByte];
+ int valInt = valByte >> ( 8 - ( posBit + 1 ) ) & 0x0001;
+ return valInt;
+ }
+
+
+ /**
+ * Set a bit in a byte array at a given position.
+ *
+ * @param data The data to set the bit in.
+ * @param pos The position of the bit to set.
+ * @param The value to set the bit to.
+ */
+ private static void setBit( byte[] data, int pos, int val )
+ {
+ int posByte = pos / 8;
+ int posBit = pos % 8;
+ byte oldByte = data[posByte];
+ oldByte = ( byte ) ( ( ( 0xFF7F >> posBit ) & oldByte ) & 0x00FF );
+ byte newByte = ( byte ) ( ( val << ( 8 - ( posBit + 1 ) ) ) | oldByte );
+ data[posByte] = newByte;
+ }
+}
Propchange: directory/apacheds/branches/kerberos-encryption-types/kerberos-shared/src/main/java/org/apache/directory/server/kerberos/shared/crypto/encryption/NFold.java
------------------------------------------------------------------------------
svn:eol-style = native
Added: directory/apacheds/branches/kerberos-encryption-types/kerberos-shared/src/test/java/org/apache/directory/server/kerberos/shared/crypto/encryption/NFoldTest.java
URL: http://svn.apache.org/viewvc/directory/apacheds/branches/kerberos-encryption-types/kerberos-shared/src/test/java/org/apache/directory/server/kerberos/shared/crypto/encryption/NFoldTest.java?view=auto&rev=533933
==============================================================================
--- directory/apacheds/branches/kerberos-encryption-types/kerberos-shared/src/test/java/org/apache/directory/server/kerberos/shared/crypto/encryption/NFoldTest.java
(added)
+++ directory/apacheds/branches/kerberos-encryption-types/kerberos-shared/src/test/java/org/apache/directory/server/kerberos/shared/crypto/encryption/NFoldTest.java
Mon Apr 30 21:06:47 2007
@@ -0,0 +1,306 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+package org.apache.directory.server.kerberos.shared.crypto.encryption;
+
+
+import java.util.Arrays;
+
+import junit.framework.TestCase;
+
+
+/**
+ * Tests the use of "n-folding" using test vectors from RFC 3961,
+ * "Encryption and Checksum Specifications for Kerberos 5."
+ *
+ * @author <a href="mailto:dev@directory.apache.org">Apache Directory Project</a>
+ * @version $Rev$, $Date$
+ */
+public class NFoldTest extends TestCase
+{
+ /**
+ * Tests an n-fold test vector from RFC 3961.
+ */
+ public void testNFold1()
+ {
+ int n = 64;
+ String passPhrase = "012345";
+
+ int k = passPhrase.getBytes().length * 8;
+ int lcm = NFold.getLcm( n, k );
+ assertEquals( "LCM", 192, lcm );
+
+ byte[] nFoldValue = NFold.nFold( n, passPhrase.getBytes() );
+
+ byte[] testVector =
+ { ( byte ) 0xbe, ( byte ) 0x07, ( byte ) 0x26, ( byte ) 0x31, ( byte ) 0x27,
( byte ) 0x6b, ( byte ) 0x19,
+ ( byte ) 0x55 };
+ assertTrue( Arrays.equals( nFoldValue, testVector ) );
+ }
+
+
+ /**
+ * Tests an n-fold test vector from RFC 3961.
+ */
+ public void testNFold2()
+ {
+ int n = 56;
+ String passPhrase = "password";
+
+ int k = passPhrase.getBytes().length * 8;
+ int lcm = NFold.getLcm( n, k );
+ assertEquals( "LCM", 448, lcm );
+
+ byte[] nFoldValue = NFold.nFold( n, passPhrase.getBytes() );
+
+ byte[] testVector =
+ { ( byte ) 0x78, ( byte ) 0xa0, ( byte ) 0x7b, ( byte ) 0x6c, ( byte ) 0xaf,
( byte ) 0x85, ( byte ) 0xfa };
+ assertTrue( Arrays.equals( nFoldValue, testVector ) );
+ }
+
+
+ /**
+ * Tests an n-fold test vector from RFC 3961.
+ */
+ public void testNFold3()
+ {
+ int n = 64;
+ String passPhrase = "Rough Consensus, and Running Code";
+
+ int k = passPhrase.getBytes().length * 8;
+ int lcm = NFold.getLcm( n, k );
+ assertEquals( "LCM", 2112, lcm );
+
+ byte[] nFoldValue = NFold.nFold( n, passPhrase.getBytes() );
+
+ byte[] testVector =
+ { ( byte ) 0xbb, ( byte ) 0x6e, ( byte ) 0xd3, ( byte ) 0x08, ( byte ) 0x70,
( byte ) 0xb7, ( byte ) 0xf0,
+ ( byte ) 0xe0 };
+ assertTrue( Arrays.equals( nFoldValue, testVector ) );
+ }
+
+
+ /**
+ * Tests an n-fold test vector from RFC 3961.
+ */
+ public void testNFold4()
+ {
+ int n = 168;
+ String passPhrase = "password";
+
+ int k = passPhrase.getBytes().length * 8;
+ int lcm = NFold.getLcm( n, k );
+ assertEquals( "LCM", 1344, lcm );
+
+ byte[] nFoldValue = NFold.nFold( n, passPhrase.getBytes() );
+
+ byte[] testVector =
+ { ( byte ) 0x59, ( byte ) 0xe4, ( byte ) 0xa8, ( byte ) 0xca, ( byte ) 0x7c,
( byte ) 0x03, ( byte ) 0x85,
+ ( byte ) 0xc3, ( byte ) 0xc3, ( byte ) 0x7b, ( byte ) 0x3f, ( byte ) 0x6d,
( byte ) 0x20,
+ ( byte ) 0x00, ( byte ) 0x24, ( byte ) 0x7c, ( byte ) 0xb6, ( byte ) 0xe6,
( byte ) 0xbd,
+ ( byte ) 0x5b, ( byte ) 0x3e };
+ assertTrue( Arrays.equals( nFoldValue, testVector ) );
+ }
+
+
+ /**
+ * Tests an n-fold test vector from RFC 3961.
+ */
+ public void testNFold5()
+ {
+ int n = 192;
+ String passPhrase = "MASSACHVSETTS INSTITVTE OF TECHNOLOGY";
+
+ int k = passPhrase.getBytes().length * 8;
+ int lcm = NFold.getLcm( n, k );
+ assertEquals( "LCM", 7104, lcm );
+
+ byte[] nFoldValue = NFold.nFold( n, passPhrase.getBytes() );
+
+ byte[] testVector =
+ { ( byte ) 0xdb, ( byte ) 0x3b, ( byte ) 0x0d, ( byte ) 0x8f, ( byte ) 0x0b,
( byte ) 0x06, ( byte ) 0x1e,
+ ( byte ) 0x60, ( byte ) 0x32, ( byte ) 0x82, ( byte ) 0xb3, ( byte ) 0x08,
( byte ) 0xa5,
+ ( byte ) 0x08, ( byte ) 0x41, ( byte ) 0x22, ( byte ) 0x9a, ( byte ) 0xd7,
( byte ) 0x98,
+ ( byte ) 0xfa, ( byte ) 0xb9, ( byte ) 0x54, ( byte ) 0x0c, ( byte ) 0x1b
};
+ assertTrue( Arrays.equals( nFoldValue, testVector ) );
+
+ }
+
+
+ /**
+ * Tests an n-fold test vector from RFC 3961.
+ */
+ public void testNFold6()
+ {
+ int n = 168;
+ String passPhrase = "Q";
+
+ int k = passPhrase.getBytes().length * 8;
+ int lcm = NFold.getLcm( n, k );
+ assertEquals( "LCM", 168, lcm );
+
+ byte[] nFoldValue = NFold.nFold( n, passPhrase.getBytes() );
+
+ byte[] testVector =
+ { ( byte ) 0x51, ( byte ) 0x8a, ( byte ) 0x54, ( byte ) 0xa2, ( byte ) 0x15,
( byte ) 0xa8, ( byte ) 0x45,
+ ( byte ) 0x2a, ( byte ) 0x51, ( byte ) 0x8a, ( byte ) 0x54, ( byte ) 0xa2,
( byte ) 0x15,
+ ( byte ) 0xa8, ( byte ) 0x45, ( byte ) 0x2a, ( byte ) 0x51, ( byte ) 0x8a,
( byte ) 0x54,
+ ( byte ) 0xa2, ( byte ) 0x15 };
+ assertTrue( Arrays.equals( nFoldValue, testVector ) );
+ }
+
+
+ /**
+ * Tests an n-fold test vector from RFC 3961.
+ */
+ public void testNFold7()
+ {
+ int n = 168;
+ String passPhrase = "ba";
+
+ int k = passPhrase.getBytes().length * 8;
+ int lcm = NFold.getLcm( n, k );
+ assertEquals( "LCM", 336, lcm );
+
+ byte[] nFoldValue = NFold.nFold( n, passPhrase.getBytes() );
+
+ byte[] testVector =
+ { ( byte ) 0xfb, ( byte ) 0x25, ( byte ) 0xd5, ( byte ) 0x31, ( byte ) 0xae,
( byte ) 0x89, ( byte ) 0x74,
+ ( byte ) 0x49, ( byte ) 0x9f, ( byte ) 0x52, ( byte ) 0xfd, ( byte ) 0x92,
( byte ) 0xea,
+ ( byte ) 0x98, ( byte ) 0x57, ( byte ) 0xc4, ( byte ) 0xba, ( byte ) 0x24,
( byte ) 0xcf,
+ ( byte ) 0x29, ( byte ) 0x7e };
+ assertTrue( Arrays.equals( nFoldValue, testVector ) );
+ }
+
+
+ /**
+ * Tests an n-fold test vector from RFC 3961.
+ */
+ public void testNFoldKerberos64()
+ {
+ int n = 64;
+ String passPhrase = "kerberos";
+
+ int k = passPhrase.getBytes().length * 8;
+ int lcm = NFold.getLcm( n, k );
+ assertEquals( "LCM", 64, lcm );
+
+ byte[] nFoldValue = NFold.nFold( n, passPhrase.getBytes() );
+
+ byte[] testVector =
+ { ( byte ) 0x6b, ( byte ) 0x65, ( byte ) 0x72, ( byte ) 0x62, ( byte ) 0x65,
( byte ) 0x72, ( byte ) 0x6f,
+ ( byte ) 0x73 };
+ assertTrue( Arrays.equals( nFoldValue, testVector ) );
+ }
+
+
+ /**
+ * Tests an n-fold test vector from RFC 3961.
+ */
+ public void testNFoldKerberos128()
+ {
+ int n = 128;
+ String passPhrase = "kerberos";
+
+ int k = passPhrase.getBytes().length * 8;
+ int lcm = NFold.getLcm( n, k );
+ assertEquals( "LCM", 128, lcm );
+
+ byte[] nFoldValue = NFold.nFold( n, passPhrase.getBytes() );
+
+ byte[] testVector =
+ { ( byte ) 0x6b, ( byte ) 0x65, ( byte ) 0x72, ( byte ) 0x62, ( byte ) 0x65,
( byte ) 0x72, ( byte ) 0x6f,
+ ( byte ) 0x73, ( byte ) 0x7b, ( byte ) 0x9b, ( byte ) 0x5b, ( byte ) 0x2b,
( byte ) 0x93,
+ ( byte ) 0x13, ( byte ) 0x2b, ( byte ) 0x93 };
+ assertTrue( Arrays.equals( nFoldValue, testVector ) );
+ }
+
+
+ /**
+ * Tests an n-fold test vector from RFC 3961.
+ */
+ public void testNFoldKerberos168()
+ {
+ int n = 168;
+ String passPhrase = "kerberos";
+
+ int k = passPhrase.getBytes().length * 8;
+ int lcm = NFold.getLcm( n, k );
+ assertEquals( "LCM", 1344, lcm );
+
+ byte[] nFoldValue = NFold.nFold( n, passPhrase.getBytes() );
+
+ byte[] testVector =
+ { ( byte ) 0x83, ( byte ) 0x72, ( byte ) 0xc2, ( byte ) 0x36, ( byte ) 0x34,
( byte ) 0x4e, ( byte ) 0x5f,
+ ( byte ) 0x15, ( byte ) 0x50, ( byte ) 0xcd, ( byte ) 0x07, ( byte ) 0x47,
( byte ) 0xe1,
+ ( byte ) 0x5d, ( byte ) 0x62, ( byte ) 0xca, ( byte ) 0x7a, ( byte ) 0x5a,
( byte ) 0x3b,
+ ( byte ) 0xce, ( byte ) 0xa4 };
+ assertTrue( Arrays.equals( nFoldValue, testVector ) );
+ }
+
+
+ /**
+ * Tests an n-fold test vector from RFC 3961.
+ */
+ public void testNFoldKerberos256()
+ {
+ int n = 256;
+ String passPhrase = "kerberos";
+
+ int k = passPhrase.getBytes().length * 8;
+ int lcm = NFold.getLcm( n, k );
+ assertEquals( "LCM", 256, lcm );
+
+ byte[] nFoldValue = NFold.nFold( n, passPhrase.getBytes() );
+
+ byte[] testVector =
+ { ( byte ) 0x6b, ( byte ) 0x65, ( byte ) 0x72, ( byte ) 0x62, ( byte ) 0x65,
( byte ) 0x72, ( byte ) 0x6f,
+ ( byte ) 0x73, ( byte ) 0x7b, ( byte ) 0x9b, ( byte ) 0x5b, ( byte ) 0x2b,
( byte ) 0x93,
+ ( byte ) 0x13, ( byte ) 0x2b, ( byte ) 0x93, ( byte ) 0x5c, ( byte ) 0x9b,
( byte ) 0xdc,
+ ( byte ) 0xda, ( byte ) 0xd9, ( byte ) 0x5c, ( byte ) 0x98, ( byte ) 0x99,
( byte ) 0xc4,
+ ( byte ) 0xca, ( byte ) 0xe4, ( byte ) 0xde, ( byte ) 0xe6, ( byte ) 0xd6,
( byte ) 0xca, ( byte ) 0xe4 };
+ assertTrue( Arrays.equals( nFoldValue, testVector ) );
+ }
+
+
+ /**
+ * Test one's complement addition (addition with end-around carry). Note
+ * that for purposes of n-folding, we do not actually complement the
+ * result of the addition.
+ */
+ public void testSum()
+ {
+ byte[] n1 =
+ { ( byte ) 0x86, ( byte ) 0x5E };
+ byte[] n2 =
+ { ( byte ) 0xAC, ( byte ) 0x60 };
+ byte[] n3 =
+ { ( byte ) 0x71, ( byte ) 0x2A };
+ byte[] n4 =
+ { ( byte ) 0x81, ( byte ) 0xB5 };
+
+ byte[] sum = NFold.sum( n1, n2, n1.length * 8 );
+ sum = NFold.sum( sum, n3, sum.length * 8 );
+ sum = NFold.sum( sum, n4, sum.length * 8 );
+
+ byte[] result = new byte[]
+ { ( byte ) 0x25, ( byte ) 0x9F };
+ assertTrue( Arrays.equals( sum, result ) );
+ }
+}
Propchange: directory/apacheds/branches/kerberos-encryption-types/kerberos-shared/src/test/java/org/apache/directory/server/kerberos/shared/crypto/encryption/NFoldTest.java
------------------------------------------------------------------------------
svn:eol-style = native
|