Re: Decimal encryption

2008-08-28 Thread Hal Finney
I wrote:
 Looking a little more closely, I found this paper by Patarin from
 Crypto 2005 which describes security bounds for higher round Feistel
 constructions:

 http://www.springerlink.com/content/gtcabev3ucv8apdu/

I was wrong, this was from Crypto 03. And as Eric Rescorla has already
pointed out, Patarin had an improved the result the following year where
he showed that 6 rounds was sufficient for security.

Greg Rose wrote:
  So, you don't have a 133-bit block cipher lying around? No worries, I'll
  sell you one ;-). Actually that is easy too. Take a trustworthy 128-bit
  block cipher like AES. To encrypt, do:
 
  1. Encrypt the first 128 bits (ECB mode)
  2. Encrypt the last 128 bits (also ECB mode).

 Hal Finney wrote:
  I am not familiar with the security proof here, do you have a reference?
  Or is it an exercise for the student?

 It's a degenerate case of Rivest's All-or-nothing transform (which 
 applies to larger, multi-block blocks, if you know what I mean :-) ). I 
 believe he gave a security proof, some 6ish years ago. But I could be 
 confabulating.

Hmmm, looking at Rivest's package transform which was his original
proposal for an AONT, that seems to be different and actually expanded
the message size. I haven't been able to find an AONT which is quite
like this.

One limitation with this proposal is that it appears that it will only
be as strong as the size of the overlapping region. However in this case
the overlap is 128-5 or 123 bits, so the birthday bound will be about
2^62 rather than the ideal 2^64, and that is hardly noticeable. So it
does seem like it could be a good choice here. Doing a little over 3 AES
encryptions will be much better than the 6 which seem to be necessary for
the Feistel approach. However such a substantial improvement certainly
makes a proof of security more interesting.

Hal Finney

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-28 Thread Hovav Shacham

- Jonathan Katz [EMAIL PROTECTED] wrote:

 But he probably wants an encryption scheme, not a cipher.

Jon, I'm not sure I understand what you mean.

If I am reading his message correctly, the original poster seems
to be asking for a format-preserving encryption over a domain
with 10^40 elements.  Format-preserving, it seems to me, implies
[a family of keyed] functions that are one-to-one and
deterministic.  In other words, the best security we can hope for
is a PRP on that domain, and this is what B-R gives, starting
from a PRP over a somewhat larger domain.

In this setting, what is the difference between an encryption
scheme and a cipher?

 Also, correct me if I am wrong, but Black and Rogaway's
 approach is not efficient for large domains. But if you use
 their approach for small domains then you open yourself up to
 dictionary attacks.

I think the dependency depends on the amount by which the domain
of the constructed PRP is smaller than the domain of the starting
PRP.  A 133-bit B-R would indeed be inefficient to construct from
a 256-bit block cipher like Rijndael, and one would need a
different starting point; but these could be constructed using a
Feistel of appropriate size.

Is the dictionary attack problem any more severe than for any
other PRP over a small domain?  The best one can hope for is a
security guarantee for a number of queries approaching the size
of the domain -- or to ensure that in practical deployment access
to the encryption and decryption functionality is constrained.

Yours --
Hovav.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-28 Thread Peter Gutmann
Eric Rescorla [EMAIL PROTECTED] writes:

There are a set of techniques that allow you to encrypt elements of arbitrary
sets back onto that set.

... and most of them seem to be excessively complicated for what they end up
achieving.  Just for reference the mechanism from the sci.crypt thread of more
than a decade ago was:

KSG_RANGE = ( 256 / RANGE ) * RANGE;

do
val = ksg();
while( val = KSG_RANGE );

  The worst-case scenario is when RANGE = 129, when nearly 50% of the ksg()
  output will be discarded.  A more typical case when RANGE = 96 (ASCII text)
  loses 25% of the output, and RANGE = 10 (digits) loses 2% of the output. The
  full process then becomes:

  encrypt:

do
val = ksg();
while( val = KSG_RANGE );
cipher = ( ( ( plain - BASE ) + val ) % RANGE ) + BASE;

  decrypt:

do
val = ksg();
while( val = KSG_RANGE );
plain = ( ( ( cipher - BASE ) - val ) % RANGE );
while( plain  0 )
plain += RANGE;
plain += BASE; 

This takes any cipher (block or stream) and, by using it as a KSG, allows
encryption of arbitrary (including discontinuous) data ranges.

Another advantage of the KSG use is that you can precalculate the key stream
offline, the implementation I used at the time pre-generated 4K of keystream
and then used it to encrypt bursty text messages with real-time constraints
that didn't allow for pauses to run the cipher.

(The thread contains lots of tweaks and variations of this).

Peter.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-28 Thread Eric Rescorla
At Thu, 28 Aug 2008 17:32:10 +1200,
Peter Gutmann wrote:
 
 Eric Rescorla [EMAIL PROTECTED] writes:
 
 There are a set of techniques that allow you to encrypt elements of arbitrary
 sets back onto that set.
 
 ... and most of them seem to be excessively complicated for what they end up
 achieving.  Just for reference the mechanism from the sci.crypt thread of more
 than a decade ago was:

[Description of reduced-range stream cipher elided]


 Another advantage of the KSG use is that you can precalculate the key stream
 offline, the implementation I used at the time pre-generated 4K of keystream
 and then used it to encrypt bursty text messages with real-time constraints
 that didn't allow for pauses to run the cipher.
 
 (The thread contains lots of tweaks and variations of this).

There's noting inherently wrong with this mechanism, but like all
stream ciphers, it can't be used if you want to encrypt multiple
independent values, e.g., credit cards in a database--without
a randomizer (which implies expansion) you have the usual two-time
pad problems. A B-R style block cipher can, albeit with lookup
table issues.

-Ekr

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-28 Thread Jonathan Katz

On Wed, 27 Aug 2008, Eric Rescorla wrote:


At Wed, 27 Aug 2008 16:10:51 -0400 (EDT),
Jonathan Katz wrote:


On Wed, 27 Aug 2008, Eric Rescorla wrote:


At Wed, 27 Aug 2008 17:05:44 +0200,
There are a set of techniques that allow you to encrypt elements of
arbitrary sets back onto that set.

The original paper on this is:
John Black and Phillip Rogaway. Ciphers with arbitrary ?nite domains. In
CT-RSA, pages 114?130, 2002.


But he probably wants an encryption scheme, not a cipher.


Hmm... I'm not sure I recognize the difference between encryption
scheme and cipher. Can you elaborate?


A block cipher is a primitive that can be used, in particular, to 
construct encryption schemes. But you can construct encryption schemes 
without block ciphers, and you can use block ciphers to construct other 
things besides encryption. Moreover, good encryption should generally 
be randomized, while a block cipher is deterministic.


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-28 Thread Jonathan Katz

On Wed, 27 Aug 2008, Hovav Shacham wrote:


- Jonathan Katz [EMAIL PROTECTED] wrote:


But he probably wants an encryption scheme, not a cipher.


Jon, I'm not sure I understand what you mean.

If I am reading his message correctly, the original poster seems
to be asking for a format-preserving encryption over a domain
with 10^40 elements.  Format-preserving, it seems to me, implies
[a family of keyed] functions that are one-to-one and
deterministic.  In other words, the best security we can hope for
is a PRP on that domain, and this is what B-R gives, starting
from a PRP over a somewhat larger domain.

In this setting, what is the difference between an encryption
scheme and a cipher?


Yes, I can see this might cause confusion.

Just to clarify: I had emailed the original poster off-line and he
told me that he was willing to use other information already being
sent in the clear as a non-repeating IV. Given this, secure (and, in
particular, non-deterministic) encryption is possible.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-28 Thread Thomas Baignères

Hello,

Actually, block ciphers encrypting blocks of *decimal* numbers exist:

- TOY100 [1] encrypts blocks of 32 decimal digits
- DEAN18 [2] encrypts blocks of 18 decimal digits
- DEAN27 [3] encrypts blocks of 27 decimal digits

TOY100 is (almost) broken by the generalized linear cryptanalysis  
described in [2]. Both versions of DEAN are based on a substitution  
permutation network very close to that of the AES and are provably  
secure against linear cryptanalysis. These ciphers are only toy  
ciphers. Consequently, there is no official implementation (no test- 
vector, etc.).


Here are the references:
[1] Granboulan, Levieil, Piret: Pseudorandom Permutation Families over  
Abelian Groups. FSE 2006: 57-77
[2] Baignères, Stern, Vaudenay: Linear Cryptanalysis of Non Binary  
Ciphers. Selected Areas in Cryptography 2007: 184-211 (available here: http://lasecwww.epfl.ch/~tbaigner/papers/groupLC.pdf 
 )
[3] Baignères (PhD Thesis): Quantitative Security of Block Ciphers:  
Designs and Security Tools (to be published)


I hope this helps. I'm of course available for any question regarding  
DEANxx.


Best regards,
Thomas Baignères
--
http://lasecwww.epfl.ch/~tbaigner

On Aug 27, 2008, at 5:05 PM, Philipp Gühring wrote:


Hi,

I am searching for symmetric encryption algorithms for decimal  
strings.


Let's say we have various 40-digit decimal numbers:
2349823966232362361233845734628834823823
3250920019325023523623692235235728239462
0198230198519248209721383748374928601923

As far as I calculated, a decimal has the equivalent of about 3,3219
bits, so with 40 digits, we have about 132,877 bits.

Now I would like to encrypt those numbers in a way that the result  
is a

decimal number again (that's one of the basic rules of symmetric
encryption algorithms as far as I remember).

Since the 132,877 bits is similar to 128 bit encryption (like eg.  
AES),
I would like to use an algorithm with a somewhat comparable strength  
to AES.

But the problem is that I have 132,877 bits, not 128 bits. And I can't
cut it off or enhance it, since the result has to be a 40 digit  
decimal

number again.

Does anyone know a an algorithm that has reasonable strength and is  
able

to operate on non-binary data? Preferrably on any chosen number-base?

Best regards,
Philipp Gühring

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-28 Thread Greg Rose
One of the earlier messages (I lost it) said that Philipp said that 
there was information that could be used as a nonce. In that case, I 
would recommend a stream cipher used to generate 133 bits at a time; if 
the lump of bits represents an integer in the correct range, add it 
modulo 10^40... otherwise generate more bits. This is about as simple as 
it gets.


Greg.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Decimal encryption

2008-08-27 Thread Philipp Gühring
Hi,

I am searching for symmetric encryption algorithms for decimal strings.

Let's say we have various 40-digit decimal numbers:
2349823966232362361233845734628834823823
3250920019325023523623692235235728239462
0198230198519248209721383748374928601923

As far as I calculated, a decimal has the equivalent of about 3,3219
bits, so with 40 digits, we have about 132,877 bits.

Now I would like to encrypt those numbers in a way that the result is a
decimal number again (that's one of the basic rules of symmetric
encryption algorithms as far as I remember).

Since the 132,877 bits is similar to 128 bit encryption (like eg. AES),
I would like to use an algorithm with a somewhat comparable strength to AES.
But the problem is that I have 132,877 bits, not 128 bits. And I can't
cut it off or enhance it, since the result has to be a 40 digit decimal
number again.

Does anyone know a an algorithm that has reasonable strength and is able
to operate on non-binary data? Preferrably on any chosen number-base?

Best regards,
Philipp Gühring

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-27 Thread Eric Rescorla
At Wed, 27 Aug 2008 17:05:44 +0200,
Philipp Gühring wrote:
 
 Hi,
 
 I am searching for symmetric encryption algorithms for decimal strings.
 
 Let's say we have various 40-digit decimal numbers:
 2349823966232362361233845734628834823823
 3250920019325023523623692235235728239462
 0198230198519248209721383748374928601923
 
 As far as I calculated, a decimal has the equivalent of about 3,3219
 bits, so with 40 digits, we have about 132,877 bits.
 
 Now I would like to encrypt those numbers in a way that the result is a
 decimal number again (that's one of the basic rules of symmetric
 encryption algorithms as far as I remember).
 
 Since the 132,877 bits is similar to 128 bit encryption (like eg. AES),
 I would like to use an algorithm with a somewhat comparable strength to AES.
 But the problem is that I have 132,877 bits, not 128 bits. And I can't
 cut it off or enhance it, since the result has to be a 40 digit decimal
 number again.
 
 Does anyone know a an algorithm that has reasonable strength and is able
 to operate on non-binary data? Preferrably on any chosen number-base?

There are a set of techniques that allow you to encrypt elements of
arbitrary sets back onto that set. 

The original paper on this is:
John Black and Phillip Rogaway. Ciphers with arbitrary ?nite domains. In 
CT-RSA, pages 114?130, 2002. 

For a modern proposal to make this a NIST mode, see:
http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffsem/ffsem-spec.pdf

-Ekr

Full Disclosure: Terence Spies, the author of the FFSEM proposal,
works for Voltage, Voltage has a product based on this technology.
and I'm on Voltage's TAB and have done some work for them.
 

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-27 Thread Peter Gutmann
=?ISO-8859-15?Q?Philipp_G=FChring?= [EMAIL PROTECTED] writes:

Does anyone know a an algorithm that has reasonable strength and is able to
operate on non-binary data? Preferrably on any chosen number-base?

I posted a description of how to perform encryption in limited subranges to
sci.crypt about ten years ago,
http://groups.google.com/groups?hl=enlr=ie=UTF-8threadm=5c8sin%24piv%40scream.auckland.ac.nzrnum=1prev=/groups%3Fq%3D%2B%2522ASCII%2522%2Bgroup:sci.crypt%2Bauthor:Peter%2Bauthor:Gutmann%26hl%3Den%26lr%3D%26ie%3DUTF-8%26as_drrb%3Db%26as_mind%3D12%26as_minm%3D5%26as_miny%3D1996%26as_maxd%3D17%26as_maxm%3D7%26as_maxy%3D1998%26selm%3D5c8sin%2524piv%2540scream.auckland.ac.nz%26rnum%3D1,
the code and a cleaned-up description is also in Building Secure
Software by John Viega and Gary McGraw.

Peter.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-27 Thread Steven M. Bellovin
On Wed, 27 Aug 2008 17:05:44 +0200
Philipp G__hring [EMAIL PROTECTED] wrote:

 Hi,
 
 I am searching for symmetric encryption algorithms for decimal
 strings.
 
 Let's say we have various 40-digit decimal numbers:
 2349823966232362361233845734628834823823
 3250920019325023523623692235235728239462
 0198230198519248209721383748374928601923
 
 As far as I calculated, a decimal has the equivalent of about 3,3219
 bits, so with 40 digits, we have about 132,877 bits.
 
 Now I would like to encrypt those numbers in a way that the result is
 a decimal number again (that's one of the basic rules of symmetric
 encryption algorithms as far as I remember).
 
 Since the 132,877 bits is similar to 128 bit encryption (like eg.
 AES), I would like to use an algorithm with a somewhat comparable
 strength to AES. But the problem is that I have 132,877 bits, not 128
 bits. And I can't cut it off or enhance it, since the result has to
 be a 40 digit decimal number again.
 
 Does anyone know a an algorithm that has reasonable strength and is
 able to operate on non-binary data? Preferrably on any chosen
 number-base?
 
Do you want a stream cipher or a block cipher?  For the former, it's
easy.  Use something like rc4, which produces a sequence of keystream
bytes.  Retrieve the low-order N bits from each key stream byte, where N
is large enough for the base you're using.  If the value is greater
than or equal to the base you're using, discard that byte and try
again.  For your example, you'd use the low-order 4 bits, but discard
any bytes whose value is = 10.  Add this value, discarding the carry,
to the digit to be encrypted.

You're running RC4 at 5/8 efficiency; unless you have a *lot* of data,
that almost certainly doesn't matter.


--Steve Bellovin, http://www.cs.columbia.edu/~smb

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-27 Thread Thierry Moreau



Philipp Gühring wrote:


Hi,

I am searching for symmetric encryption algorithms for decimal strings.

Let's say we have various 40-digit decimal numbers:
2349823966232362361233845734628834823823
3250920019325023523623692235235728239462
0198230198519248209721383748374928601923

As far as I calculated, a decimal has the equivalent of about 3,3219
bits, so with 40 digits, we have about 132,877 bits.

Now I would like to encrypt those numbers in a way that the result is a
decimal number again (that's one of the basic rules of symmetric
encryption algorithms as far as I remember).

Since the 132,877 bits is similar to 128 bit encryption (like eg. AES),
I would like to use an algorithm with a somewhat comparable strength to AES.
But the problem is that I have 132,877 bits, not 128 bits. And I can't
cut it off or enhance it, since the result has to be a 40 digit decimal
number again.

Does anyone know a an algorithm that has reasonable strength and is able
to operate on non-binary data? Preferrably on any chosen number-base?



The short answer is no, nobody knows a secure algorithm that would 
work as a decimal stream cipher AND would not extend the message size 
for some form of key material reference data (or salt or IV ...).


If you have room for such message-specific reference data, it should be 
easy to design a decimal stream cipher for short messages.



--

- Thierry Moreau

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-27 Thread Greg Rose

Philipp Gühring wrote:

Hi,


G'day Philipp,


I am searching for symmetric encryption algorithms for decimal strings.

Let's say we have various 40-digit decimal numbers:
2349823966232362361233845734628834823823
3250920019325023523623692235235728239462
0198230198519248209721383748374928601923

As far as I calculated, a decimal has the equivalent of about 3,3219
bits, so with 40 digits, we have about 132,877 bits.

Now I would like to encrypt those numbers in a way that the result is a
decimal number again (that's one of the basic rules of symmetric
encryption algorithms as far as I remember).

Since the 132,877 bits is similar to 128 bit encryption (like eg. AES),
I would like to use an algorithm with a somewhat comparable strength to AES.
But the problem is that I have 132,877 bits, not 128 bits. And I can't
cut it off or enhance it, since the result has to be a 40 digit decimal
number again.

Does anyone know a an algorithm that has reasonable strength and is able
to operate on non-binary data? Preferrably on any chosen number-base?


There is a fairly standard technique for handling things like this.

1. encode your number N into a 133-bit string S
2. encrypt S with your favourite 133-bit block cipher (see below)
3. decode S to a number N'
4. if N' = 10^40, goto 2 (that is, re-encrypt until it is in range)
5. N' is your answer.

This is uniquely invertible, although a little slow (since on average it 
will take 8.9% or so more encryptions because of the inner loop, and 
some side-channel information leaks when it does the extra encryptions. 
Decryption is exactly the same operation except step 2 uses decryption 
mode of the block cipher.


So, you don't have a 133-bit block cipher lying around? No worries, I'll 
sell you one ;-). Actually that is easy too. Take a trustworthy 128-bit 
block cipher like AES. To encrypt, do:


1. Encrypt the first 128 bits (ECB mode)
2. Encrypt the last 128 bits (also ECB mode).

To decrypt, do decryptions in the reverse order, obviously. It's easy to 
see that this is a secure permutation if AES itself is, depending on 
your definition of secure; if you add a third step, to re-encrypt the 
first 128 bits, it is truly secure. (Without the third step, tweaking a 
bit in the first 5 bits will often leave the last 5 unchanged on 
decryption, which is clearly a distinguishing attack; the third 
encryption makes it an all-or-nothing transform.)


I believe the above gives you a secure enough block cipher on 40 digit 
strings, and if you only ever encrypt single chunks, ECB mode should be 
fine... of course that depends on the real threat analysis of your 
system. It does about 2.19 AES encryptions per 40 digits, should be fast 
enough.


hope that helps,
Greg.

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-27 Thread Hal Finney
Philipp Gühring writes:
 I am searching for symmetric encryption algorithms for decimal strings.

 Let's say we have various 40-digit decimal numbers:
 2349823966232362361233845734628834823823
 3250920019325023523623692235235728239462
 0198230198519248209721383748374928601923

 As far as I calculated, a decimal has the equivalent of about 3,3219
 bits, so with 40 digits, we have about 132,877 bits.

Right, although as an American I was confused for a moment until I
remembered the European convention of using comma for the decimal point,
while we use period. But you are right and it was my mistake.

 Now I would like to encrypt those numbers in a way that the result is a
 decimal number again (that's one of the basic rules of symmetric
 encryption algorithms as far as I remember).

 Since the 132,877 bits is similar to 128 bit encryption (like eg. AES),
 I would like to use an algorithm with a somewhat comparable strength to AES.
 But the problem is that I have 132,877 bits, not 128 bits. And I can't
 cut it off or enhance it, since the result has to be a 40 digit decimal
 number again.

This is a very common question. Unfortunately the state of the art in
cryptography does not as far as I know have a good answer. The most recent
analysis I found is http://www.cs.ucdavis.edu/~rogaway/papers/subset.pdf
from CT-RSA 2002 by Black and Rogaway.

Basically they propose what is called a Luby-Rackoff construction,
related to another construction called a Feistel network. Unfortunately
their analysis does not show that this is secure, but I believe that by
adding more steps it can be made so.

The idea is to start with your 40 digit number and split it into two parts
of 20 digits. Call the left part L and the right part R. Then repeatedly
execute the following steps:

L = (L xor AES(R)) mod 10^20
(L,R) = (R,L) (i.e. interchange L and R)

After doing this a certain number of steps, interchange L and R one
last time, and concatenate L and R to get your output. (Equivalently,
skip the interchange of L and R on the last step.)

Now, it is important in doing this that AES have a different key for
each round or step. You can start with a single key K, and generate
the round keys as K0 = AES(K,0), K1 = AES(K,1), K2 = AES(K,2), and so on.

To decrypt, the same basic process is used. But this time, use the round
keys in the reverse order. Instead of K0, K1, K2, use K2, K1, K0.

Black and Rogaway analyzed for just 3 rounds, and they found basically
that for your case, this construction would only have about 32 bits of
strength; that is, after encrypting about 4 billion numbers, you would
be losing security.  If you are only ever encrypting many fewer numbers
than this (with a given key), it should probably be OK.

The other possibility is to increase the number of rounds. The paper
hints that this will help but does not offer any specific analysis. I saw
a speculative comment online that 8 rounds would be strong. I believe
that going back to the Luby-Rackoff paper may offer some guidance,
but I don't have time to do that now.

Note that this unfortunately does not get the benefit you were hoping for
from being so close to the AES block size. While there are some known
tricks for dealing with being a little shorter than the cipher block,
I couldn't find any good ones for being a few bits longer.

Hal Finney

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-27 Thread Jonathan Katz

On Wed, 27 Aug 2008, Eric Rescorla wrote:


At Wed, 27 Aug 2008 17:05:44 +0200,
Philipp Gühring wrote:


Hi,

I am searching for symmetric encryption algorithms for decimal strings.

Let's say we have various 40-digit decimal numbers:
2349823966232362361233845734628834823823
3250920019325023523623692235235728239462
0198230198519248209721383748374928601923

As far as I calculated, a decimal has the equivalent of about 3,3219
bits, so with 40 digits, we have about 132,877 bits.

Now I would like to encrypt those numbers in a way that the result is a
decimal number again (that's one of the basic rules of symmetric
encryption algorithms as far as I remember).

Since the 132,877 bits is similar to 128 bit encryption (like eg. AES),
I would like to use an algorithm with a somewhat comparable strength to AES.
But the problem is that I have 132,877 bits, not 128 bits. And I can't
cut it off or enhance it, since the result has to be a 40 digit decimal
number again.

Does anyone know a an algorithm that has reasonable strength and is able
to operate on non-binary data? Preferrably on any chosen number-base?


There are a set of techniques that allow you to encrypt elements of
arbitrary sets back onto that set.

The original paper on this is:
John Black and Phillip Rogaway. Ciphers with arbitrary ?nite domains. In
CT-RSA, pages 114?130, 2002.


But he probably wants an encryption scheme, not a cipher.

Also, correct me if I am wrong, but Black and Rogaway's approach is not 
efficient for large domains. But if you use their approach for small 
domains then you open yourself up to dictionary attacks.



For a modern proposal to make this a NIST mode, see:
http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffsem/ffsem-spec.pdf

-Ekr

Full Disclosure: Terence Spies, the author of the FFSEM proposal,
works for Voltage, Voltage has a product based on this technology.
and I'm on Voltage's TAB and have done some work for them.


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-27 Thread lists
Philipp Gühring wote:

 I am searching for symmetric encryption algorithms for decimal strings.
 
 Let's say we have various 40-digit decimal numbers:
 2349823966232362361233845734628834823823
 3250920019325023523623692235235728239462
 0198230198519248209721383748374928601923
 
 As far as I calculated, a decimal has the equivalent of about 3,3219
 bits, so with 40 digits, we have about 132,877 bits.

English readers normally use . as the decimal point - you had me confused
for a few seconds and maybe it wasn't only me.

Regardless of the calculated bit-equivalent you aren't storing these strings
in 132.877 bits - but possibly 40*8 bits, 40*4 bits or in some other way.
 
 Now I would like to encrypt those numbers in a way that the result is a
 decimal number again (that's one of the basic rules of symmetric
 encryption algorithms as far as I remember).

I don't think that's a feature of the encryption as such.
 
 Since the 132,877 bits is similar to 128 bit encryption (like eg. AES),
 I would like to use an algorithm with a somewhat comparable strength to AES.
 But the problem is that I have 132,877 bits, not 128 bits. And I can't
 cut it off or enhance it, since the result has to be a 40 digit decimal
 number again.

This sounds like possible confusion over block length and key size.  Then
you get involved in padding and storage of a slightly larger ciphertext.
 
 Does anyone know a an algorithm that has reasonable strength and is able
 to operate on non-binary data? Preferrably on any chosen number-base?

It sounds as if you want a stream cipher arrangement that you could make
out of a normal binary stream cipher by:
   read a byte of the keystream
   if  9 reject it and take the next one (aiming for uniform distribution)
   if the value is [0-9] add it to the current plaintext digit mod 10

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-27 Thread Steven M. Bellovin
On Wed, 27 Aug 2008 09:34:15 -0700
Greg Rose [EMAIL PROTECTED] wrote:
 
 So, you don't have a 133-bit block cipher lying around? No worries,
 I'll sell you one ;-). 

Also see Debra Cook's PhD dissertation on Elastic Block Ciphers at
http://www1.cs.columbia.edu/~dcook/thesis_ab.shtml



--Steve Bellovin, http://www.cs.columbia.edu/~smb

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-27 Thread Eric Rescorla
At Wed, 27 Aug 2008 16:10:51 -0400 (EDT),
Jonathan Katz wrote:
 
 On Wed, 27 Aug 2008, Eric Rescorla wrote:
 
  At Wed, 27 Aug 2008 17:05:44 +0200,
  There are a set of techniques that allow you to encrypt elements of
  arbitrary sets back onto that set.
 
  The original paper on this is:
  John Black and Phillip Rogaway. Ciphers with arbitrary ?nite domains. In
  CT-RSA, pages 114?130, 2002.
 
 But he probably wants an encryption scheme, not a cipher.

Hmm... I'm not sure I recognize the difference between encryption
scheme and cipher. Can you elaborate?


 Also, correct me if I am wrong, but Black and Rogaway's approach is not 
 efficient for large domains. But if you use their approach for small 
 domains then you open yourself up to dictionary attacks.

I suppose it depends what you mean by small and large.

A lot of the relevant values are things like SSNs, CCNs, etc.
which fall in the 10-20 digit category, where the Luby-Rackoff
approach is efficient. As I understand the situation, the
cycle following approach is efficient as long as the set
is reasonably close to the L-R block size. 

As far as dictionary attacks go, for any small domain permutation
you have to worry about table construction attacks. The only 
defense I know of is randomized encryption which defeats the
non-expansion requirement.

WRT to the security of the L-R construction, Spies claims that
I believe that Patarin's 2004 result [0] is relevant here, but
I'm not qualified to evaluate it. Anyway, the reference I provided
earlier [1] provides a summary of the claimed security properties
of L-R + Cycle Following.

-Ekr

[0] Jacques Patarin. Security of random feistel schemes with 5 or more rounds. 
In Matthew K. Franklin, editor, CRYPTO, volume 3152 of Lecture Notes in 
Computer Science, pages 106?122. Springer, 2004. 

[1] http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/
ffsem/ffsem-spec.pdf

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-27 Thread Hal Finney
I like Greg Rose's solution best:

 There is a fairly standard technique for handling things like this.

 1. encode your number N into a 133-bit string S
 2. encrypt S with your favourite 133-bit block cipher (see below)
 3. decode S to a number N'
 4. if N' = 10^40, goto 2 (that is, re-encrypt until it is in range)
 5. N' is your answer.

This is Rich Schroeppel's trick from his Hasty Pudding cipher, a somewhat
under-rated AES submission IMO. HPC originated not only this trick,
but also the idea of tweakable encryption, which has turned out to be
important for disk encryption. The Black-Rogaway paper referenced earlier
has a proof of security of this construction.

 So, you don't have a 133-bit block cipher lying around? No worries, I'll 
 sell you one ;-). Actually that is easy too. Take a trustworthy 128-bit 
 block cipher like AES. To encrypt, do:

 1. Encrypt the first 128 bits (ECB mode)
 2. Encrypt the last 128 bits (also ECB mode).

I didn't understand this at first, but I finally saw that the point is to
do the encryptions in-place; step 1 replaces the first 128 bits of the
data with the encryption, and similarly for step 2. This is equivalent
to doing CBC mode with a fixed IV of 0, and ciphertext stealing for the
final partial block of 5 bits.

 To decrypt, do decryptions in the reverse order, obviously. It's easy to 
 see that this is a secure permutation if AES itself is, depending on 
 your definition of secure; if you add a third step, to re-encrypt the 
 first 128 bits, it is truly secure. (Without the third step, tweaking a 
 bit in the first 5 bits will often leave the last 5 unchanged on 
 decryption, which is clearly a distinguishing attack; the third 
 encryption makes it an all-or-nothing transform.)

I am not familiar with the security proof here, do you have a reference?
Or is it an exercise for the student?

Hal Finney

-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]


Re: Decimal encryption

2008-08-27 Thread Greg Rose

Hal Finney wrote:

So, you don't have a 133-bit block cipher lying around? No worries, I'll
sell you one ;-). Actually that is easy too. Take a trustworthy 128-bit
block cipher like AES. To encrypt, do:

1. Encrypt the first 128 bits (ECB mode)
2. Encrypt the last 128 bits (also ECB mode).


I didn't understand this at first, but I finally saw that the point is to
do the encryptions in-place; step 1 replaces the first 128 bits of the
data with the encryption, and similarly for step 2. This is equivalent
to doing CBC mode with a fixed IV of 0, and ciphertext stealing for the
final partial block of 5 bits.


Yes, I guess it is... hadn't thought of it that way. But yes, I confirm 
that I meant to do the encryptions in place.



To decrypt, do decryptions in the reverse order, obviously. It's easy to
see that this is a secure permutation if AES itself is, depending on
your definition of secure; if you add a third step, to re-encrypt the
first 128 bits, it is truly secure. (Without the third step, tweaking a
bit in the first 5 bits will often leave the last 5 unchanged on
decryption, which is clearly a distinguishing attack; the third
encryption makes it an all-or-nothing transform.)


I am not familiar with the security proof here, do you have a reference?
Or is it an exercise for the student?


It's a degenerate case of Rivest's All-or-nothing transform (which 
applies to larger, multi-block blocks, if you know what I mean :-) ). I 
believe he gave a security proof, some 6ish years ago. But I could be 
confabulating.


-
The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]