2
$\begingroup$

I'm encrypting with an FPE algorithm in C#. What I did is convert the date I want to encrypt to the day of year value and a year value like so.

string input = "1901-01-01";
DateTimeOffset parsedDateOffset = new DateTimeOffset();
bool parsed = false;
parsed = DateTimeOffset.TryParseExact(input, "yyyy-MM-dd", CultureInfo.InvariantCulture, DateTimeStyles.AllowWhiteSpaces, out parsedDateOffset);

if(parsed){

    DateTime dtNew = new DateTime(parsedDateOffset.Year, parsedDateOffset.Month, parsedDateOffset.Day);
    int dayOfYear = dtNew.DayOfYear;
    int yyyy = parsedDateOffset.Year;

// Then I encrypt the day of year separate from the year

    int encodedDay = FE11.Encrypt(365, dayOfYear, Encoding.UTF8.GetBytes(input.ToString()), Encoding.UTF8.GetBytes("0"));
    int encodedYear= FE11.Encrypt(2015 - 1901, yyyy, Encoding.UTF8.GetBytes(input.ToString()), Encoding.UTF8.GetBytes("0"));

// Then combine them together again taking into account leap year

     DateTime encodedDate = new DateTime((int)encodedYear, 1, 1).AddDays((int)encodedDay - 1);;
     if (DateTime.IsLeapYear((int)encodedYear))
     {
         encodedDate.AddDays(1);
     }   
}

However I'm encountering duplicate dates (i.e. for two plaintext dates result in the same encrypted date) But with format preserving encryption this should not be the case, and I know it is because of the way I am emcrypting the year separate from the day of year.

Does anyone have any suggestion to overcome this? I have tried introducing a tweak but the problem persists.

Ideally I would like to encrypt only one value. But encrypting the day of year alone still requires me to place it in the context of a year when presenting the final encrypted result.

Are there other date representation besides day of year that might be useful?

EDIT: The FPE library I am using at this time is called DotFPE located here https://dotfpe.codeplex.com/ (which is supposedly a port of the Format Preserving module of Botan Crypto)

$\endgroup$
  • $\begingroup$ What FPE library are you using? Can you give us a link to it? $\endgroup$ – mikeazo Aug 6 '15 at 17:11
  • $\begingroup$ @mikeazo ok, added that detail at the end of my original post $\endgroup$ – erotavlas Aug 6 '15 at 17:24
  • $\begingroup$ Can you provide some sample outputs? Are the values duplicate right after the call to Encrypt or not until you call AddDays? $\endgroup$ – mikeazo Aug 6 '15 at 17:29
  • $\begingroup$ Also, when I look at the code, Encrypt takes 4 parameters, not 3 like you show in your example code. What am I missing? $\endgroup$ – mikeazo Aug 6 '15 at 17:32
  • $\begingroup$ @mikeazo sorry it was the key, I updated the post. BTW I'm using the original date as the key using Encoding.UTF8.GetBytes(input.ToString()) since I only care to encrypt one way, no need to decrypt. $\endgroup$ – erotavlas Aug 6 '15 at 17:47
6
$\begingroup$

So, in the comments, you state that

I'm using the original date as the key

This is the reason for the duplicate dates. The encryption is entirely deterministic for a fixed key. When you change the key, however, it is not. So it is entirely plausible that encrypting the number 215 with the key 215 could result in the same ciphertext as encrypting the number 10 with the key 10. But, encrypting the numbers 215 and 10 each with the same key, say 111, should be guaranteed to result in different ciphertexts (assuming you are not using the tweak, or using a fixed tweak).

If you had a fixed, random key, then you should get different ciphertexts. Adding in a random, per-message "tweak" can also cause this behavior.

So you can fix this "problem" by just using the same key everywhere and no tweak. This does, however, scare me. You are using deterministic encryption in an application that has a fairly small domain. Could make you vulnerable to frequency attacks, or other attacks, depending on the exact application.

$\endgroup$
  • $\begingroup$ I probably wouldn't use a single key for everything, since my goal by changing the key for each input was to make it difficult to decipher. I think I'm going to try ponchos suggestion and use the Timespan in days since a start date, that way I encrypt only one value instead of two separate. $\endgroup$ – erotavlas Aug 6 '15 at 18:05
  • 1
    $\begingroup$ I don't think that over 15000 duplicates would be out of the ordinary. Here is some python code I wrote that generates 42003 random numbers between 0 and 42003 (inclusive) and counts how many duplicates there are. Running it, I was getting around 15500 duplicates. $\endgroup$ – mikeazo Aug 6 '15 at 19:17
  • 1
    $\begingroup$ @erotavlas, I asked this question to get a better answer for you. $\endgroup$ – mikeazo Aug 6 '15 at 20:55
  • 1
    $\begingroup$ @erotavias, the longer the input the better. $\endgroup$ – mikeazo Aug 6 '15 at 23:10
  • 1
    $\begingroup$ @erotavlas it has little to do with FPE and everything to do with the output space. It is the birthday problem $\endgroup$ – mikeazo Aug 7 '15 at 0:24
3
$\begingroup$

One potential reason you might be running into duplicates is if you encrypt 'December 31' of a leap year; that makes it day 366, and that's out of range for your FPE method.

The obvious way to address this (and encrypt both days and years together) would be to convert the value into "days since January 1, 1901", encrypt that as a value between 0 and 42003 (the number of days between January 1, 1901 and December 31, 2015), and then convert that back into the standard format.

$\endgroup$
  • $\begingroup$ Actually I corrected for leap year. My modulus is set to 365 to yield an encrypted value between 0 - 364 (or 1 - 365) Once I obtain the day value, if the year value I use is a leap year according to DateTime.IsLeapYear() method I add an extra day to the result. Not sure if that is correct way, but it did seem to work. $\endgroup$ – erotavlas Aug 6 '15 at 17:52
  • 1
    $\begingroup$ @erotavlas, if you are always adding 1, doesn't that make January 1 of leap years impossible? $\endgroup$ – mikeazo Aug 6 '15 at 18:04
  • $\begingroup$ oops, yeah that's right. I'd need to change the modulus instead, have one encryption that gives leap years and another for regular years. $\endgroup$ – erotavlas Aug 6 '15 at 18:22
  • $\begingroup$ @erotavlas the nice thing about using this encoding is that you don't have to work around leap year corner cases. $\endgroup$ – mikeazo Aug 6 '15 at 19:33
  • 1
    $\begingroup$ And, it doesn't leak if two encrypted dates are from the same year; if the attacker sees 'Jan 23, 1932' and 'November 19, 1932', with your encoding, they don't know the year, but they can deduce both were from the same one. $\endgroup$ – poncho Aug 6 '15 at 19:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.