"be consistent" PerlMonks

### Deterministic asymmetric encryption [Crypt::RSA]

by andreas1234567 (Vicar)
 on Dec 15, 2010 at 14:14 UTC Need Help??
andreas1234567 has asked for the wisdom of the Perl Monks concerning the following question:

I'm looking for deterministic asymmetric encryption (The "database search" example given in the wikipedia article is very closely related to mine):
A deterministic encryption scheme (as opposed to a probabilistic encryption scheme) is a cryptosystem which always produces the same ciphertext for a given plaintext and key, even over separate executions of the encryption algorithm. Examples of deterministic encryption algorithms include the RSA cryptosystem (without encryption padding)
The documentation for Crypt::RSA specifically says:
[..] there exists a scheme called Simple RSA[16] that provides security without padding. However, Crypt::RSA doesn't implement this scheme yet.
Is there a CPAN module that implements deterministic asymmetric encryption?
```\$ perl -l
use strict;
use warnings;

use Log::Log4perl;
use Crypt::RSA;

my \$rsa = new Crypt::RSA;
my (\$public, \$private) = \$rsa->keygen(
Identity  => 'Lord Macbeth <macbeth@glamis.com>',
Size      => 1024,
Password  => 'A day so foul & fair',
Verbosity => 0,
) or die \$rsa->errstr();

my \$secret = q{Thanks for all the fish};

my \$ciphertext1 =
\$rsa->encrypt(Message => \$secret, Key => \$public, Armour => 1,)
|| die \$rsa->errstr();
my \$ciphertext2 =
\$rsa->encrypt(Message => \$secret, Key => \$public, Armour => 1,)
|| die \$rsa->errstr();

\$ciphertext1 eq \$ciphertext2 ? print q{deterministic} : print q{not de
+terministic};

__END__

not deterministic
\$
Update: What would the consequences be if I disregarded the advise in the documentation:
In any event, Crypt::RSA::Primitives (without padding) should never be used directly.
```my \$prim = new Crypt::RSA::Primitives;
my \$ctxt1 = \$prim->core_encrypt (Key => \$public, Plaintext => \$pan);
my \$ctxt2 = \$prim->core_encrypt (Key => \$public, Plaintext => \$pan);
\$ctxt1 eq \$ctxt2 ? print q{deterministic} : print q{not deterministic}
+;
Prints "deterministic".
--
No matter how great and destructive your problems may seem now, remember, you've probably only seen the tip of them. [1]

Replies are listed 'Best First'.
Re: Deterministic asymmetric encryption [Crypt::RSA]
by ikegami (Pope) on Dec 15, 2010 at 16:53 UTC

Crypt::CBC with just about any back end (incl, say, Crypt::Rijndael) and a constant IV would qualify as a deterministic encryption scheme. That's why it's a red flag whenever someone specifies an IV to Crypt::CBC.

Why do you want this? It seriously weakens the encryption. Maybe what you really need is a hashing algorithm.

Crypt::CBC with just about any back end (incl, say, Crypt::Rijndael)
Wouldn't that be Symmetric-key encryption, and not asymmetric encryption as the title suggests?
Why do you want this? It seriously weakens the encryption. Maybe what you really need is a hashing algorithm.
I realize it weakens the encryption. The question is how much?

My motivation is similar to the one described here:

One primary motivation for the use of deterministic encryption is the efficient searching of encrypted data. Suppose a client wants to outsource a database to a possibly untrusted database service provider. If each entry is encrypted using a public-key cryptosystem, anyone can add to the database, and only the distinguished "receiver" who has the secret key can decrypt the database entries.
• I want to let anyone (any authorized local user) add to a database. E.g. add(encrypt("A")).
• I want the same users to see if a specific entry has been previously added. E.g. exists(encrypt("A")). This is where the deterministic requirement comes from.
• I will only let users in possession of a secret key decrypt the data.
• The secret key must not be stored on the server offering the services above.

If I understand it correctly, the 4 above requirements can only be accomplished using deterministic asymmetric encryption.

--
No matter how great and destructive your problems may seem now, remember, you've probably only seen the tip of them. [1]

Wouldn't that be Symmetric-key encryption, and not asymmetric encryption as the title suggests?

Oops, yes.

I realize it weakens the encryption. The question is how much?

First, it introduces information leakage. If two records have the same plain text, the creator of one of those records knows the content of the other record. If the plain text is a password, for example, this could allow someone to know someone else's password.

The other concern is that by having more blocks encrypted with the same key, one might be able to attack certain algorithms and maybe even recover the key. The potential impact of using the same key could be lessened if chaining is used (i.e. if the key used to encrypt one block depends on the previous block).

Lots of factors affect how much this matters.

I want to let anyone (any authorized local user) add to a database. E.g. add(encrypt("A")).

It doesn't have to be deterministic to do that. The requirement to use salt (iv) doesn't prevent anyone from adding to the database as long as the salt is included in the database as well.

I want the same users to see if a specific entry has been previously added. E.g. exists(encrypt("A")).

This requires deterministic encryption or hashing. Hashing algorithms have been vetted against these attacks. A particular encryption algorithms? dunno.

So you need deterministic asymmetric encryption, or non-deterministic asymmetric encryption plus hashing.

What if you have: 1) The database server in the data warehouse, with no keys. 2) A small privileged server under your control with both keys 3) Users with the public key

When adding an entry, the request goes through the privileged server. It then adds the item to the database, encrypted with the public key. It also updates a table of contents, encrypted with the private key.

The private key does not reside on the foreign database server, only on a small stateless proxy server which you fully control.

It would probably work better if you just had a really strong "any" encryption and the proxy server for doing writes. Plus the table of contents that anybody with a login can read straight from the database.

Re: Deterministic asymmetric encryption [Crypt::RSA]
by Anonyrnous Monk (Hermit) on Dec 15, 2010 at 14:47 UTC
What would the consequences be if I disregarded the advise...

As you've shown in your update, you'd get deterministic encryption — with the security disadvantages as (for example) mentioned in the Wikipedia article you linked to.

What I don't understand is what motivated you to want deterministic encryption in the first place, if you then ask what the consequences are? An XY problem? Or am I missing something?

What I don't understand is what motivated you to want deterministic encryption in the first place
I want to be able to do database lookups on the encrypted text. I also want to understand the extent of the security consequences of using deterministic encryption. E.g. is the encryption highly insecure when padding is not used, or is it just marginally less secure?
--
No matter how great and destructive your problems may seem now, remember, you've probably only seen the tip of them. [1]
Re: Deterministic asymmetric encryption [Crypt::RSA]
by sundialsvc4 (Abbot) on Dec 15, 2010 at 21:34 UTC

The approach that I would take here is ... secure the channel.   Use certificates to authenticate the users (and to secure the communications with each).   Use existing standard protocols to do this, not one that you have rolled.   Put the information on a highly-secured server which will only communicate with bearers of currently-valid credentials.   The information that passes through the secured channel can be plaintext, since it passes between parties with mutually-assured identities.   The database files are encrypted using a key known only to the server:   these services are already readily-available in any major server.   I would advocate avoiding use of deterministic encryption altogether, because I do not think it will ever provide the data-security and data-integrity that you need.

I fail to see why you should be having to “roll your own anything” to accomplish this...   This is hardly an atypical or novel requirement.

secure the channel.
I will protect data in transit. I also need to protect data at rest. Either is not sufficient.
The database files are encrypted using a key known only to the server:
Security regulations (e.g. like this) require protection against insider threats to make sure data does not escape, e.g. when backed up. To have a (symmetric) key and the data on the same server is out of question.
I would advocate avoiding use of deterministic encryption altogether, because I do not think it will ever provide the data-security and data-integrity that you need.
I would normally agree, but in this case I feel the disadvantage of a less secure encryption model is probably outweighted by the advantages of not having the (symmetric) key and the data on the same server.

There are apparently advances in cryptography research (e.g. here (RSA-DOAEP), here, and here) that suggests that deterministic asymmetric encryption is becoming increasingly secure. It takes of course a long time for new algorithms to find its way into actual, usable implmentations.

This is hardly an atypical or novel requirement.
I would compare it with to store data encrypted on your server that a root user does not have access to. I would be glad to use an of-the-shelf solution. Do such exist?

--
No matter how great and destructive your problems may seem now, remember, you've probably only seen the tip of them. [1]

Don't know how secure deterministic asymmetric encryption (lets call it DAE) is, but you want it to fill out exactly the role for which hashes aka trap-door functions were invented.

I'm actually working in a facility for cryptographic research and I asked someone who should know the actual research in the field. He told me that there is not much research about the strength of DAE, I suspect because there are much better alternatives.

Usually you would do the following: Store the data with symmetric encription and a random key that is encrypted with asymmetric encryption (this method is standard for any data bigger than a few hundred bytes, since asymmetric encryption is very slow). Beside this store the hash of the data. At the moment sha256 seems to be the hash everyone uses, with sha512 for the really paranoid.

As you can see this fulfills all your requirements

Create A New User
Node Status?
node history
Node Type: perlquestion [id://877274]
Approved by marto
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (6)
As of 2018-04-23 16:14 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
My travels bear the most uncanny semblance to ...

Results (85 votes). Check out past polls.

Notices?