An IPv6 Secret Address Generation Algorithm

Tags

client, ipv6, messaging, random, security

How would two clients communicate over IPv6 without a third-party knowing which addresses are used? This is one of the abstract problems I tried to solve back in 2013, when developing the idea of a secure messaging client that makes use of certain features associated with IPv6 (many thanks to Sam Bowne and Chris Tubb for the inspiration). It was based on two assumptions: a) both parties are assigned a block of IPv6 addresses rather than a single address, and b) communicating parties are able to arbitrarily select addresses from within their address ranges.

Address Spaces and Allocations
Given the number of possible IPv6 addresses (2^38 minus a few reserved address ranges), it’s possible that a person would be assigned a sizeable block of addresses from this, such as a 32-bit address space with 4294967296 possible addresses.

I’ve done a bit of research to determine the likely address space a person would typically be assigned. RFC 6177 reccommends allocating /48 blocks to each individual ISP customer. Whether this would actually happen in the real world remains to be seen – it’s also strongly recommended because IPv6 removes the requirement for Network Address Translation, which in turns means that an ideal allocation for a home network would be large enough to make network enumeration a little more time consuming.
IPv6 also allows for stateless address configuration, which should enable clients to select their own addresses, although this depends on how the local router is configured.

The Address Generation Algorithm
My solution is something like:

The session key is secret between two clients – how they share this is another problem which might require out-of-band communication using a public key system. Actually my proposal would be a good candidate for an instant messaging system or social network that works alongside Dark Mail.

The second parameter is the system time, in ‘HHMM’ format, because the algorithm should generate a different IPv6 address every x number of minutes, and HHMM should also be the same for both communicating clients. With a little more coding later, two clients might get this value from a shared source, perhaps over NTP.

Python Implementation
The following imports are required for implementing the concept as a Python script:
* string
* hashlib
* netaddr
* pprint
* time.gmtime and time.strftime

New addresses are generated from a current IPv6 address and a session key that might be shared between peers. These might be read from an application database and/or network interface.


selfAddress = '3ffe:1900:4545:0003:0200:f8ff:fe21:67cf'
selfKey = 'mypassword123'
peerAddress = ' '
peerKey = ' '
currentTime = strftime("%H%M")


In order to get the current address, we require a networking/NIC module that enables us to select the network interface to read from. I’m most of the way through coding a C# version of the client, using System.Net.NetworkInformation to populate a drop-down list of interfaces.

Using the netaddr and pprint modules, an address can be formatted as a hexadecimal string – basically to get the digits without the octet delimiters. The line ‘selfAddressToHex[2:]‘ removes the ‘0x‘ characters from the output.


ip = IPAddress(0, 6)
ip = IPNetwork(selfAddress)
selfAddressToHex = hex(ip.ip)
selfAddressString = selfAddressToHex[2:]


Then a SHA256 fingerprint is generated with [sessionKey+HHMM] as inputs.


hashInput = (selfKey + currentTime)
print('Hash Input: ' + hashInput)
hashedValue = hashlib.sha256(hashInput)
hashedValueString = (hashedValue).hexdigest()
print('SHA256 Fingerprint: ' + hashedValueString)


Now we can substitute the last eight bytes of the current IP address with the last eight bytes of the SHA256 value to generate a new address:


final32 = hashedValueString[56:64]
print('New Suffix: ' + final32)
newAddressString = selfAddressString.replace(selfAddressString[24:32], final32)


Finally, reformat the hex string as a valid IPv6 address by adding the delimiters between octets:


newAddress = ':'.join([newAddressString[i:i+4] for i in range(0, len(newAddressString), 4)])
print('New Address: ' + newAddress)


The running script will produce something like:

We can later write newAddress back to the application database as ‘currentAddress’, and have something that triggers this part of the application every 15 minutes.
There are other things I’d like to build on this, namely components for setting newAddress as the local IP address, and messaging between two clients running the script.

RSA PRNGs as Code

Tags

crypto, cryptopp, encryption, error, generator, number, prime, program, random, reference, relative, rng, rsa, undefined

Here’s the basic problem I was trying to solve: The RSA encryption software must use keys derived from two very large numbers that must be co-prime. I’ll explain in a later post exactly where this fits in. In the real world, they’ll be somewhere around 60 digits in length, so obviously it’s impractical to expect the user to set these numbers.
The numbers could be built into the program, but that would defeat the principle that a cipher should be fully distributable without compromising security. That leaves us with the option of generating the keys randomly, so they’ll be unique for each session. For this a Pseudo-Random Number Generator (PRNG) is needed.

I started off by copying a simple C++ example from a site, which basically uses the system clock and the rand() function.

Defining the Output Range
With most applications we might want only values within a defined range. For example, a dice program would have a range between 1 – 6.
For the RSA program, we’re using a much bigger range, both numbers having a specific number of digits. For now, I’ve set this as 1000000 – 999999 by declaring values LowerLimit and UpperLimit as constants, but it should really be much larger as FirstRandomInt and SecondRandomInt have been declared as long integers in my program (meaning a lot of unused buffer space).

The following is what generates both numbers:
FirstRandomInt = rand() % (UpperLimit - LowerLimit + 1) + time(NULL);
SecondRandomInt = rand() % (UpperLimit - LowerLimit + 1) + time(NULL);

The larger the numbers, the harder it’ll be to predict in advance the values generated, and consequently the keys also become harder to guess.

Relative Primes
Thanks to the Cryptology lectures, I’ve not only found a way to generate a pair of pseudo-random numbers with the right number of digits, but also values that are relative primes. This is what I had problems with when developing the RSA part of the XeroCrypt software last year. In this case it’s a simple matter of dropping the random number generator code into an earlier program, then making it loop.

The modified code works roughly like this: The program generates a pair of pseudo-random numbers using rand() and the system clock, passes them to a function that calculates their greatest common denominator (using the Eclidean algorithm), and repeats the entire process until the GCD is exactly 1 (indicating the numbers are co-prime). The pseudo-code looks something like:


FindGCD(FirstRandomInt, SecondRandomInt)
{
Calculate GCD of the two numbers
Pass GCD to Main()
}

Main()
{
While GCD > 1
{
Generate two random numbers
Pass RandomInt1 and RandomInt2 to FindGCD()
}
Print FirstRandomInt
Print SecondRandomInt
}


Adventures with Crypto++
While the basic PRNG that does what I need, it’s a bit crap. A real-world RSA system would use a Cryptographically Secure Pseudo-Random Number Generator (CSPRNG). Without this, we potentially have a flaw that enables an attacker to derive the keys. A suitable PRNG must meet several criteria:
* The output should be impossible to predict, beyond the fact the numbers are co-prime and within a certain range.
* The PRNG’s output must be independent of external factors, that is an attacker cannot influence the numbers it generates. For example, by changing the room temperature or causing a power surge.
* Ideally the output would be checked to ensure all the output values are uniformly distributed. There shouldn’t be any tendency to generate certain values.

Using one of the PRNGs that came with Crypto++ (such as the Mersenne Twister) would have been an excellent way of getting started with it, I wanted it done with fewer lines of code. The first step was to copy a very simple program to check whether the IDE was linking to the Crypto++ library. It wasn’t.

The program compiled okay, but attempts to build it threw up several ‘undefined reference’ errors. Basically it meant the compiler doesn’t know where the relevant Crypto++ libraries are. A quick Google (actually an IXquick) search revealed that numerous others had experiencing the same problem.
The problem’s sorted by appending -lcrypto++ to g++ compile and build commands, so the compiler knows what it’s supposed to link to. It also turns out headers in the program must be defined in the form: ‘#include "cryptopp/randpool.h"‘.

While I haven’t got the PRNG code itself working yet using Crypto++, I kind of got sidetracked into building another program that uses the AES function to encrypt any 256-character message.

RSA and XeroCrypt

Tags

asymmetric, basic, crypto, cryptography, cryptosystem, encryption, key, number, prime, random, rng, rsa, symmetric, visual, xerocrypt

(Reposted and edited from my old blog)

The XeroCrypt Application RSA Module

RSA is an asymmetric cryptosystem which uses two different keys – a public key that’s distributed to anyone wanting to encrypt and send information, and a secret key (also known as the private key) that’s used for decrypting the information. It means anyone can encrypt a message and only the recipient can decrypt it. As no secret key is being communicated, this solves the problem of how to communicate securely without a third party being able to decrypt anything. Interestingly, it would also mean a person couldn’t be later forced to reveal whatever they encrypted, since they only have the public key of the recipient. In theory, once something’s encrypted with RSA, it’s unrecoverable by the sender. In practice an plaintext copy is usually recoverable. RSA itself is normally used for safely communicating keys a symmetric key cryptographic system that requires less computing resources, such as AES and Triple-DES.

This post is my attempt to break RSA this down into simple terms, and explain how the RSA Cryptography module for the XeroCrypt software will function when I finally get it working (hopefully sometime next week).

The basic algorithm is:

The algorithm itself is very straightforward, but writing the program that does this is turning out to be easier said than done. The first problem was in finding a method of generating the first two prime numbers, since in real-life they’re at least 60 digits in length and the user can’t be expected to readily choose them. To solve this, I’m attempting to add a Random Number Generator that produces random primes up to 99999, because the program works with much shorter numbers just to demonstrate the principle. This would also provide a solution for selecting an encryption exponent (E). I should point out the RNG used in the current version of XeroCrypt isn’t actually random enough for commercial encryption, but that’s a subject to be covered in future.
The second problem is finding the right value for the decryption exponent (D). This could also be solved using a loop that tests different values for D until the calculation produces 1 as the output.

So the key generation part of the program will do something like the following:

The other two parts of the program are for encrypting and decrypting a number, using mathematical functions and some of the values (the public and private keys) produced by the key generation code.

So far the program should encrypt a number using the RSA algorithm, and some people might be wondering how this applies to the real world in which we encrypt text, images, audio, video files, etc. There are two answers to this. The first is that, as with my earlier post on XOR encryption, the content can be converted into a very long binary string – in other words, a very long number that can be used as value M in this system.