directory-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From erodrig...@apache.org
Subject svn commit: r533933 - in /directory/apacheds/branches/kerberos-encryption-types/kerberos-shared/src: main/java/org/apache/directory/server/kerberos/shared/crypto/encryption/ test/java/org/apache/directory/server/kerberos/shared/crypto/ test/java/org/ap...
Date Tue, 01 May 2007 04:06:48 GMT
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



Mime
View raw message