Algorithm to transform plaintext to a key of desired keysize, when using input plaintext as key for FPE? Using a format preserving encryption scheme that uses AES internally as its block cipher, for a plaintext that I encrypt I want to use that input plaintext as the key.

However using AES-128, my keysize is required to be 128 bit.  But i cannot guarantee my plaintext to be exactly this length - they are words or numbers of variable length.

Is there a computationally efficient and acceptably secure way to convert the plaintext to exactly the keysize required by the AES algorithm?  Does it even matter what algorithm I use?

EDIT:  The FPE I'm using is BPS.  I'm using it as a one way encryption on plaintext values such as SSN, names, dates, etc.  (Note: not using this for any authentication purposes - merely trying to eliminate the need to store or reuse a single key - I also have no need to use a single key anyway because I have no need to decrypt the original plaintext)

Further context on the answer to “Is there a format preserving cryptographically secure hash?”

EDIT 2:  Although it is convenient in the sense that this approach doesn't require storing a key anywhere I realize now that using the input plaintext as key is flawed especially for smaller plaintext which the attacker can brute force rather trivially. This is definitely not the way the FPE was designed to be used.

I'm using it as a one way encryption on plaintext values such as SSN, names, dates, etc.

I suggest rethinking your approach.  None of these values have much entropy, so it would be straightforward to bruteforce the original plaintexts (just like cracking a password hashed with a fast hash function).

If you're planning to use these values for authentication, that doesn't sound like a great idea... but I know that, in some applications, it's the best you can do.  A few suggestions:

Use a password hash instead of fancy encryption.  Since there's likely not much entropy in the secret values, a password hash would be helpful in slowing down brute force attacks.
Combine the values before hashing.  This will at least force attackers to crack them as a group, not one-at-a-time.  Be sure to combine the values such that they are delimited unambiguously.

If you must process the fields separately (in order to perform comparisons between accounts, for example), I still think a password hash is better suited to this purpose -- just use a fixed salt to make the hashing deterministic.  Don't expect too much security here though; thoroughly hashed dates can still be cracked quite easily.


Double permutation patterns for transposition ciphers, how to crack I'm reading from Cornell , I know for a single permutation, I can find the ciphertext length (100), divide in some key lengths (10x10, 5x20), then try all permutation (10x9x8... 5x4x3x2x1). then find anything legible.
Is there any case the above method will not work, and is there any better method to crack this permutation cipher?
Also, what if I use two-permutation patterns, for example; for the 100 plaintext length:

I divide it into 10 characters per column.
Then for the first 4 characters - I use one permutation.
For the next 6 characters, I use another permutation.

Am I right that this makes no difference on the cracking step?
i.e. I tried 10x10, then I tried all permutations 10! I will find anything legible.

While transposition ciphers may move bits around, they are entirely linear; and effectively perform substitution... except the data positions are substituted, instead of the values.
Let's say I have the ciphertext
raspberry
and I encrypt it to get
bsapryrre
Statistical analysis becomes even easier than with a substitution cipher: I simply look for a word or set of words with the same count of each letter. Once I have a set of possible plaintexts (there won't necessarily be only 1 match) I effectively have a reduced set of possible plaintexts, one of which forms a known plaintext.
If I have the next ciphertext block as
ip
I can perform the same attack on the next block, effectively creating a series of anagrams. In fact, this attack is so simple that it's already been implemented on every online anagram solver.
I might find multiple choices choices with meaning:

raspberry pi
raspberry ip

Since one makes more sense than the other, you know what your message is. This principal can be applied indefinitely to break transposition ciphers without even needing to break the key.


Best choice of finite field for AES on a 4-bit microcontroller? As the finite field of $GF(2^8)$ are isomorphic to $GF((2^4)^2)$, $GF((2^2)^4)$ and $GF(((2^2)^2)^2)$,
which of the fields is best suited and most efficient for 4-bit MCU and why? Would it be $GF((2^4)^2)$?

While $GF(2^8)$ is indeed isomorphic to $GF((2^4)^2)$ (and to the other fields you have mentioned), if you use the latter you will need a conversion routine to change the field representation from and to $GF(2^8)$. This will probably defeat any performance gain with the alternative representation (and I'm not sure there would be any). Another related issue is that the "nice" constants used in MixColumns (2 and 3) may not be so nice in the converted form, hurting performance when you multiply by them.

You can simply represent a $GF(2^8)$ element using two 4-bit words.


Elliptic Curve Discrete Log in a Composite Ring Elliptic curves are usually defined over prime rings (fields), but what if we chose a ring of composite order? Let $n = pq$ for $p,q$ large primes. Say I have elliptic curve $y^2 = x^3 + ax + b$ over the Ring of integers mod $n$. And I have two points on the curve, say $A, B$ such that $A = xB$. From this alone, it should be enough to determine $x$ correct? I have $n$, I have the factorization of $n = pq$, and I have $A,B$. Everything I read on elliptic curves seems to initialize over our prime field. I can find no discussion of what the actual attack is. I understand the hardness of the problem has been reduced to the integers now mod $p$ and $q$, but I don't understand the process to determine $x$ here.

Well, if you have a pseudocurve [1] based on the formula:

$$y^2 = x^3 + ax + b \pmod{ pq }$$

what you have is really two different curves stapled together; that is, the curves based on:

$$y^2 = x^3 + ax + b \pmod{ p }$$

$$y^2 = x^3 + ax + b \pmod{ q }$$

You can look at a point in the $pq$ curve as really being a point in the $p$ curve and a point in the $q$ curve; and when you perform an operation, the two component curves act independently.

So, if we denote a point $A$ as the pair $(A_p, A_q)$ and the point $B$ as the pair $(B_p, B_q)$, then the result of the point addition $A+B$ is the pair $(A_p + B_p, A_q + B_q)$, where the first addition is an addition in the $p$ curve, and the second addition is in the $q$ curve.  And if exactly one of $A_p+B_p, A_q+B_q$ is the point at infinity, then it turns out that the value $A+B$ is not defined in the $pq$ curve - that's why it's called a pseudocurve, because not all operations within the pseudocurve have defined results - it fails to be a group because it is not closed.

More to the point, if you take a point $P$ in the original $pq$, and compute $kA$, then that is equivalent:

Mapping the point $P$ to a point on the $p$ curve (by taking the $x$ and $y$ coordinates modulo $p$), and then computing $kA_p$
Mapping the point $P$ to a point on the $q$ curve (by taking the $x$ and $y$ coordinates modulo $q$), and then computing $kA_q$
Recombining $kA_p$ and $kA_q$ by reconstructing both the $x$ and $y$ coordinates using the Chinese Remainder Theorem.

With this observation, we have the following method to solve the original $A = xB$ problem:

Factor $n$ into $p, q$
Point count both the $p$ curve and the $q$ curve
Solve $A = xB$ over the $p$ curve (resulting in $x \bmod n_p$, where $n_p$ is the number of points on the $p$ curve)
Solve $A = xB$ over the $q$ curve (resulting in $x \bmod n_q$, where $n_q$ is the number of points on the $q$ curve)
Use the Chinese remainder theorem to combine $x \bmod n_p$ and $x \bmod n_q$ into $x$

These operations are jointly cheaper than solving an ECDLog problem over a prime the same size as $pq$

[1]: I'll explain why it's called pseudocurve below


Could quantum computers "break" symmetric crypto-systems (e.g. AES)? These days I'm reading about quantum computing and quantum cryptography which I've found extremely interesting. Well, I also read some blog posts of Bruce Schneier talking about how quantum computers threaten our current asymmetric crypto-systems. However, I don't know whether quantum computers also threaten symmetric crypto-systems (AES, Vernam cipher, etc.).

With Grover's algorithm, quantum computers can brute-force a block cipher with $n$-bit keys using $2^{n/2}$ steps, which is much smaller than the regular effort ($2^n$). This means, for example, that AES-128 could be broken with $2^{64}$ steps, and that AES-256 would offer the same security that AES-128 offers currently.

In short, key sizes would need to be doubled.


verify contents, but not order Is there an algorithm that can be used to verify the contents of a cyphertext, but not the order of the elements?

I am thinking that a deck of cards could be shuffled, and it must be verifiable that the deck contains all cards, but not to know what order they are in.

Any ideas how to approach this problem?

As Maeher & Codesinchaos noted you're going to want to look into Zero Knowledge protocols.
Matt Green at Hopkins wrote an easy to understand blog article that gives you one such example w.r.t. mental poker Poker is hard.
Claude Crepau wrote a fair amount in the 80s and 90s about zk/mental poker; here is a link to one paper A zero-knowledge Poker protocol that achieves confidentiality of the...

Simari has a good primer on zk here:A Primer on Zero Knowledge Protocols


Can IGE mode be parallelized? As far as I know, in IGE mode (infinite garble extension) each block depends on the previous one.

In that case, can the encryption be parallelized? Is there some way to do it?

No, the IGE encryption cannot be parallelized. Also the decryption of IGE/ABC is serial.

The input to the block cipher for encryption is the ciphertext of the previous block xor'd with the plaintext (and the result is then xor'd with the previous block plaintext).

For decryption, you have to XOR the ciphertext with the plaintext of the previous block before decrypting (and then XOR the result with the previous ciphertext).

If either ciphertext or plaintext is not available, you cannot processes the next block, or any future block.


Entropy Loss of KDFs Am I losing any entropy when using KDFs, such as the ones in NIST Special Publication 800-108?

For example, can I derive 128-bit session keys from a (uniformly random) 128-bit master key?

When you use a PRF to derive a key, there is the potential for collisions. If you derived a 128-bit key from each possible 128-bit number, you'd expect some of them to collide. Specifically, you'd expect only about 63%  of all the inputs ($1-e^{-1}$) to appear as outputs.

That means you lose less than a bit of entropy even if the original key had the full 128 bits of entropy, like your random 128-bit string. With a lower entropy key you'd lose less. That doesn't matter in practice, since in the worst case it wouldn't even halve attack time. 127-bit security is enough.

In general, if you use a PRF to derive an $n$-bit key from one with $k$ bits of entropy, the resulting key will have at least $\min(n, k) - 1$ bits of entropy, approaching $\min(n, k)$ when $k \ll n$ or $k \gg n$.


How to decrypt a short ciphertext that is said to be immune to attacks? I need to decrypt a ciphertext which is short, and I have the first word of the plaintext. I thought of doing a probable-word attack, but I already know the position of the known word.

In addition, subtracting word from cipher gives a random sequence, which makes me kind of hopeless.
So consider this is the ciphertext:

URRLMBURLQHPIFGETNIAZXTCEAHVLXKOHAHGMTP

And the first word is : somebody

I also know that the cipher is supposedly immune to statistical attacks meaning that the ratio of cipher_length/key_length is not sufficient and also I cannot notice any bigrams/trigrams for that matter.

So Vigenere is similar to caesar. So you start decrypting it like you do with caesar:

S - +2 --> U
O - +3 --> R
M - +5 --> R
E - +7 --> L
B - +11 -> M
O - +13 -> B
D - +17 -> U
Y - +19 -> R

So you may have noticed, that the text is decrypt via using the next bigger prime. Just subtract the primes from the decrypted text and you get the original message.

I did not decrypt the whole message, but i have a strong guess "Somebodyoncetoldmetheworldisgonnarollme" is the result...


Timelock puzzle improvment I came across this question with this answer about a cryptographic timelock-puzzle that needs approximately 30 years to be solved. There is also an explanation with source code for that puzzle available here and here. All of this looks very similar to RSA. My first question is: In which ways does this differ (or not differ) from RSA?

I also heard of conditions that have to be true for the chosen prime numbers in RSA to guarantee security. In the (old) source code the program just looks for the next prime number it can find. Are there any conditions for prime numbers in RSA? If so, could I implement these myself or should I use already existing code?

In RSA, exponents are small, so the encryption/decryption can be done quickly. Here, exponent is of the form $2^t$, where $t$ is very large. For example, consider RSA 2048 - exponents have at most 2048 bits. If you set $2^t=2048=2^{11}$, then to solve this puzzle one will need to do only 2048 squarings, roughly the same as you need to do a decryption in RSA. But if you set $t=2^{128}$, then one will need to do $2^{128}$ squarings, which is far outside from current computational powers.

But if you can factorize the number, then you know the order of the group and can reduce exponent modulo this order: $a^{2^t} = a^{2^t mod \phi(n)}$.

Similarity with RSA is that both problems are based on exponentiation in so-called "RSA" group (multiplication mod $pq$) and both used the fact that for an attacker the group order is unknown.

For choice of primes numbers I recommend to read the wiki article. In brief, the primes should have the same size in bits and each of the primes should be of the form $p=2q+1$, where $q$ is some another prime, to defend from Pollard's p-1 method. Also $p+1$ must also have large prime factors, to defend from Pollard's p+1 method. If you choose primes randomly of the form $p=2q+1$ then everything will be fine. Actually if you simply choose random primes of specified size (as done in the article) then chances that it is breakable are very negligible.


What's the internal state size and output range of mrg32k3a? This is Pierre L'Ecuyer's PRNG.  I know its period is $2^{191}$, but I don't know what is its internal state size.  What is it?

The answer is based on the given period construction from your link.

You have to store the two modulus

$m_1 = 2^{32} − 209 = 4294967087$ and
$m_2 = 2^{32} − 22853 = 4294944443,$

and the internal states are;

$s_{1,n} = \{x_{1,n},x_{1,n+1}, x_{1,n+1} \}$ and
$s_{2,n} = \{x_{2,n},x_{2,n+1}, x_{2,n+1} \}$.

The $z_n = (x_{1,n}- x_{2,n}) \bmod m_1$, evolves with this $x_{1,n}$ and $x_{2,n}$ where each requrrence relation for  $x_{1,n}$ and $x_{2,n}$ is taken module $m_1$ and $m_2$, respectively;

$$x_{1,n} = (1403580 \times x_{1,n-2} - 810728 \times x_{1,n-3} ) \bmod m_1,$$
$$x_{2,n} = (527612 \times x_{2,n-2} -1370589 \times x_{2,n-3} ) \bmod m_2$$

Therefore you need to store 3 moduli $m_1$ and 3 moduli $m_2$ internal states.

The $m_1$ and $m_2$ is very close to $2^{32}$, so we can say that you need;

6 unsigned 32-bit integers for the internal states.
For the modulus, you will also need 2 unsigned 32-bit integers.

the range is $m_1$ since the $z_n$ is taken $\mod m_1$.

Yes; the state for all practical purposes is $8 \cdot 32=256$-bit.


A Construction of a Cipher from a Single Pseudorandom Permutation A paper from 1997 A construction of a cipher from a single pseudorandom permutation proposes a cipher in which The message block is XORed with K1 before applying F [a single random permutation], and the outcome is XORed with K2. The authors state We show that the resulting cipher is secure (when the permutation is random or pseudorandom)

I found one paper Limitations of the Even-Mansour Construction that describes its severe limitations, but it still provoked some questions:

Is there any means to make a similarly simple cipher secure (even in theory)? How?
Might repeating further rounds make it secure against DCA?
Is there a similar cipher that 'is' useful by modern standards?

Even-Mansour is not as severely limited as you make it sound. The success probability for an attacker of Even-Mansour has been shown in various papers to be at best
$$
\text{Adv}^{SPRP}_{EM_{K_1, K_2}}(q, p) \le \frac{2qp}{2^n}\,,
$$
where $q$ is the amount of black-box queries you make to the cipher (read: known or chosen plaintexts), $p$ the number of queries you make to the permutation (read: bruteforce), and $n$ the bit width of the permutation. The same security bound applies to the single-key variant
$$
\text{SEK}_K(x) = P(x \oplus K) \oplus K.
$$
Now, this means that, unlike an optimal block cipher, in which no matter how much data you collect you still expect around $2^n$ computational effort to break it, here by collecting $q$ plaintexts the effort goes down to $2^n/q$.

Now, to answer your questions:

Even-Mansour is already secure, as long as you adequately deal with the above caveats. For example, if you choose your permutation to be, say, 512 bits wide, you have nothing to fear from any realistic attacker.
Yes, iterating several permutations does give you better security. For example, the key-alternating cipher (or iterated Even-Mansour)
$$
\text{KAC}_{K_0, K_1, K_2,\dots,K_t}(x) = P_t(P_1(x \oplus K_0) \oplus K_1) \dots) \oplus K_t
$$
achieves better security $$\text{Adv}^{SPRP}_{\text{KAC}_{K_0, K_1, K_2,\dots,K_t}}(q,p_1,p_2,\dots,p_t) \le \frac{4^tqp_1p_2\dots p_t}{2^{nt}}\,,
$$
which quickly converges to optimal as $t$ grows.
As seen above, iterating Even-Mansour is an effective way to strengthen the cipher. In practice, however, having several independent permutations and keys is inconvenient, and so you see designs that use a single permutation along with multiple round keys, each derived from a single master key. The AES is one such design, with the public permutation—the round function—being weaker than a random permutation but efficient to compute. This is a very successful design principle, and you will find many other ciphers following the same strategy.


Understanding hash entropy I have been told that one advantage of using a hash function is that it spreads entropy over all input bits. But it also seems to be true that a bad hash algorithm can make things less random. But how do I know if the hash I am using doesn’t make things less random?

Currently, I’m hashing (SHA2) a few extracted bytes I collect from a CSRNG to create keys for AES encryption/decryption. Is that wrong? From what I’ve been reading, SHA2 seems to be secure. But I could also skip SHA2 and extract more random bytes from the CSRNG until I’ve got enough bytes for a key. Is that a better idea? Or is SHA2 not one of those hashes that might make things less random?

Currently, I’m hashing (SHA2) a few extracted bytes I collect from a CSRNG to create keys for AES encryption/decryption. Is that wrong?

Depends on what you mean by "a few"; if you mean 16 or more, then yes, that is likely to be secure.  However, if you mean, say, 4, then that is Very Bad.

The reason is that the hash function doesn't do magic; if you use only 4 bytes of CSRNG output, and then compute:

$$Key := SHA256( \text{CSRNG Output} )$$

then what an attacker can do is exhaustive search over all 4 bytes of possible CSRNG output, compute the corresponding keys, and test them; there are only $2^{32}$ possibilities; a single laptop is likely to be able to go through all of them in perhaps an hour.

  But I could also skip SHA2 and extract more random bytes from the CSRNG until I’ve got enough bytes for a key. Is that a better idea?

Well, you'll likely need that many bytes of CSRNG output to form a secure AES key anyways; once you have that many, the SHA256 doesn't add anything.

  Or is SHA2 not one of those hashes that might make things less random?

No, SHA2 is not likely to be a weak hash function.  However, the problem is that SHA2 doesn't make things more random -- if there are only $2^{32}$ possible inputs to SHA2, there are only $2^{32}$ possible outputs.  It might make things look more random, but that's not what we care about.


Does a public key absolutely need to be used to initiate an encrypted session? I am a software developer working on an application with the .NET platform.  This application needs to provide a secure connection and encrypt all data between the client and the server.  It is a standaone app that does not use a web browser and will be using a symmetrical key for the vast majority of the messages for best perfomance.  Sessions can be expected to last between a few minutes to more than 24 hours.  I am somewhat of a beginner when it comes to cryptography, but I have done some research.

From the research I have done, it appears that the current thinking is to use a public/private pair of keys to initiate the session.  The first message sent by the client is encrypted with the public key, which is then decrypted by the server with a private key.  In the first message to the server, a random symmetric session key is also transmitted which is then used for the rest of the session and then discarded after use.  All this seems to be quite reasonable, but I do have some questions and concerns:

If public/private keys are to be used for the initial message, then should the same public client / server private key be used for all clients?  Or, should each user have a separate public / private key?  The application client would not need to maintain a private key for decrypting public key messages from the server since all further messages would be using symmetric encryption.  My concern is that if only one key pair is used and someone does somehow manage to figure out that private 2048-bit key, then all the users of the application would be vulnerable...
From research I have done, it looks like some are recommending that nothing less than 2048 bit RSA keys should be used.  If this application takes off, it could easily have 500,000 users within 5 years or so.  Generating public/private 2048 bit key pairs takes some time (if you know how much time it takes - please let me know along with the hardware) and with 500,000 users, could cause some serious time delays in the future.  Imagine a scenario where all of the 500,000 key pairs need to be regenerated.  How long woutd that take?  So, I'm wondering if there is another way of initiating the session that is just as good and circumvents the need to use public / private key pairs to initiate the session...
The application will have a website assocatiated with it that will allow users to register with a user id and password.  What I am thinking about doing is to apply the password to generate the initial symmetric key that would be used to encrypt the first message to the server.  The random session key would still be transmitted and used after the first message.  To identify the user, a unique user token would be supplied to the client installation upon registration that would be appended to the first encrypted message and the user token would not be encrypted.  Once the server receives the first message, it looks up the token and obtains the password.  The symmetric key for that password is then generated on the server exactly the same way as was done on the client.  The .NET platform provides a way to generate keys from a password with the PasswordDeriveBytes class.  So, this approach seems like it will work, but I am not an expert on this topic and would appreciate hearing from others who are more experienced and are in a position to point out anything that I might be missing...
I have also researched symmetric ciphers.  Since performance is an issue as well as security, I am thinking of going with CAST-128 instead of Rijndael which is now being used by just about everyone as the AES.  The reason for this is because according to some benchmarks, CAST-128 is faster on Windows systems.  Also, from a security point of view, I would much prefer to use a much less popular cipher than one that is being used by the US, other governments, and most companies.  There is much more interest in breaking Rijndael than CAST-128 which is only being used by the Canadian govt and PGP.

First recommendation: Don't invent your own protocol, but use an existing one. Use SSL/TLS, in the newest version possible if you don't have to provide downwards compatibility to existing clients. This will take care of most problems here, you simply put in a pair of plaintext data streams, and get a pair of encrypted streams. There are TLS implementations for most programming languages available, I'm quite sure that .NET has one, too.
TLS is quite flexible about the key exchange, authentication and encryption algorithms (bundled together as "cipher suite"). You'll have a public key for the server (usually with a certificate, whose subscribing key can already be embedded in the client application), and then use (for example) Diffie-Hellman key exchange with public-key authentication. There are also password-based key exchange algorithms, then you even don't need a public key (but client and server need some other way to first get the common password).
To your questions:

SSL/TLS works fine with a constant public key, not a different one per-client. Of course, if the private key gets leaked, all future connections are broken. If you did use the simple "encrypt session key by public key" model (RSA key exchange), also all past connections can be decrypted. Diffie-Hellman provides forward-secrecy, as the key is generated from random input of both sides, and the public key is only used for authentication.
If you create a new key pair per-client, you'll need some way of the client to tell its name (or key ID or similar) before the actual connection.

I have no data about how long key generation nowadays takes, sorry. You also have to take care of having enough entropy for your keys. But as said before, there is no need to generate new keys regularly.

Instead of doing this yourself, have a look on the secure remote password protocol for generating a shared session key authenticated by a password. This is also available (standardized) as a key exchange method for TLS, though I'm not sure if it is supported by .NET's implementation.

You can use whatever cipher you want, but as said by others, AES is actually more likely to be secure than other ciphers. Also, modern processors have actually AES-instructions build in, which could make the performance difference quite small or even negative (i.e. AES-128 could be faster than CAST-128), if you use a library which actually can make use of these.


Is it possible to construct a secure block cipher of size $2n$ given a secure block cipher of size $n$? Given, say, the Blowfish block cipher, which is considered secure but only has a 64-bit block size, can we construct a secure block cipher of 128-bit block size?

Say we run the key through two KDFs, and encrypt the first half of the block with the first key, and the second half of the block with the second key. This seems to give a 128-bit block cipher. However, this is probably insecure, since say if we use CTR mode both halves still become insecure by themselves.

One method of doing this would be to construct a Feistel network using the n-bit blockcipher as a round function. A drawback of this approach is that because you're using a blockcipher (a pseudo-random permutation) in place of a pseudo-random function, you are almost immediately limited to being secure to only $q \ll 2^{n/2}$ queries as a result of the Birthday Paradox. For $n = 64$, this could be quite problematic. (And I guess might be the type of scenario that led you to ask this question in the first place).

One way around this is to build a PRF $f_{K_1 K_2}(x) = E_{K_1}(x) \oplus E_{K_2}(x)$, where $E$ is your blockcipher. (See "The Sum of a PRPs is a secure PRF"). This is secure for $q \ll 2^{2n/3}$ queries. The result generalizes to $q \ll 2^{dn/(d+1)}$ when you XOR the outputs of $d$ independently keyed blockciphers. So you could use this for your round function. But since your round functions have to have different keys, you end up using a lot of key material, and there's a significant performance hit.

As an aside, there's a lot of literature on constructing $m$-bit "tweakable" blockciphers out of $n$-bit blockciphers for arbitrary $m > n$. This line of work is motivated mostly by full-disk encryption. See, for example, EME, HEH, HCTR. But almost all of these are again only secure up to $q \ll 2^{n/2}$ queries.


Is it possible to manage an encrypted dataset for face recognition? Im in my final year of PhD in computer vision and my supervisor has given me a task that I am not very familiar with. So I am teaching myself homomorphic encryption everyday. This question is mostly about clarifying my understandings as well.

He wants me to setup an encrypted dataset for an internal competition among his first year students. The task is to identify faces within the encrypted domain using homomorphic properties.

So to begin with I started reading about Paillier encryption and coded the encryption and decryption part from the equations in the literature review. So now I can encrypt data into ciphertext and decrypt that ciphertext back into its original text successfully. I then tested homomorphism and that is working as well. I can add together the ciphertexts and also multiply a scalar value to the ciphertexts. So the implementation and practical side that I taught myself was done.

I understand that in Paillier system we have a public key n (n = p * q) and g, and a private key mu and lambda. The client and the server know the public keys and the server can use this public key to perform homomorphic addition/multiplication and only the client knows the private key as only the client can decrypt the messages. Now from my understanding, his idea is for me to encrypt a simple face dataset like the ORL dataset and make available the encrypted dataset and the public keys for his students to perform operations on and hopefully determine the correct identity of another encrypted query image.

Now my main concern is about the practicality and possibility of all of this. My supervisor did not give me much details and just basically said make this happen.

My understanding is that to have a decent level of encryption for such a local dataset a n of size 1024 bits would suffice. So I should encrypt the images with a key size of 1024 and then give the encrypted dataset along with the public key to the students. Maybe I should also give the private key so that they can decrypt their results to see if they identified correctly.

Sorry for the long post but Im trying to understand is all of this possible? Can the students perform identification in the encrypted domain using only the data I provide them?

If I understand correctly, the setting describe by you is that you want to simulate a scenario where an encrypted dataset is hosted on an untrusted server, then a user can send encrypted image to it, the server blindly match the image with every encrypted image in the set, then return the user the best match. This seems not possible (at least without some carefully thought and design) because the server does not have the private key thus would not know which one is the best match. Of course the server can, for each encrypted image, return a result and the user can decrypt, then the user decide which one is the best match.

Whether the matching can be done in the encrypted domain depends much on what matching algorithm you use. Paillier is only additively homomorphic, meaning that you cannot do multiplication in the encrypted domain (except multiply a constant). The computation is restricted to an integer group, not real numbers. All of those constraints would restrict your choices, possibly only to those simple ones.


Brute-force breakability in practice determined by recognizability of plaintext? It seems to me (a non-expert obviously) that the brute-force breakability of symmetric encryption algorithms is usually (always?) expressed as "would take approximately N time on such-and-such hardware".

But in practice, how would one single attempt among trillions at finding the key be identified as "the right one" that succesfully decrypts the message? Doesn't that require the result of the attempt (i.e. the "plaintext" result) to be recognizable as such?

If yes, doesn't this mean that if the plaintext is not easily and quickly recognizable as such (as for example ASCII-encoded English prose might be), brute-force is in practice MUCH harder than the so-much-time-on-such-hardware description suggests?

And if yes, doesn't this mean that a trivial (but unknown) "pre-encryption", e.g. ROT13 or base-64 encoding makes a brute-force attack hugely more difficult?

If yes, doesn't this mean that if the plaintext is not easily and
  quickly recognizable as such (as for example ASCII-encoded English
  prose might be), brute-force is in practice MUCH harder than the
  so-much-time-on-such-hardware description suggests?

If the plaintext is not recognizable at all (random numbers (from a good generator)) and if the attacker has no other way to test if it is the real data, you are right, just brute-forcing solves nothing.

But, other than good random numbers, what kind of data is not recognizable for someone knowing a bit about computers? Text no, Images no, any file format from known programs no, any file format from unknown programs no (eg. low entropy and many more things), sometimes there are checksums as part of the data, and so on...

  And if yes, doesn't this mean that a trivial (but unknown)
  "pre-encryption", e.g. ROT13 or base-64 encoding makes a brute-force
  attack hugely more difficult?

No, ROT13, data compression and other preprocessing steps (other than good encryption with a different key) do not add security.

Because, even if the attacker doesn't know about the preprocessing step (which should not be assumed, listen to Kerckhoff), such things can be detected easily. Eg. ASCII text with ROT13 is still ASCII text (ie. A-Z), just not as readable. Getting an output with mostly english letters when trying AES keys is unusual => time look at it closer.

  The practical scenario I have in mind is the encryption of one's own
  files on disk, using a standard algorithm, e.g. AES.

Lets take a disk with 1TB. The chance that, with 2^128 keys, multiple keys lead to a sane output (each one of size 2^(8*1024*1024*1024*1024)), is pretty small. And content of a HDD with OS and music and whatever on it is easily recognizable.


Is there are a metric based on collisions to compare bad hash functions? Bad hash functions are not so perfect as in the "general collision probability"  hypothesis... And a general concept of "collision resistence"  not need the constraint  of independence between the hash function and the sample set.

Let $H$ be a hash function with digest of $k$ bits, and $S$ a input sample set with size $s=|S|$.$H$ is collision resistant if it is "hard to find" two inputs that hash to the same output,
$\exists x\ne y\in S|H(x)=H(y)$

But "hard to find" is not a good definition: to compare the performance of two hash functions $H_1$ and $H_2$ we need a precise metric... Wikipedia  use $Pr[H]$, the probability concept to define this metric... But, in real-life tests or benchmarking, we have only the number of collisions $c$, and a big standard deviation to compare $c$ values when change $S$ or $H$.

Puting the question in other words:    there are a "standard way" to obtain the real-life $Pr[H]$ of bad hash functions?

Context. Let me be a programmer that buy low quality proprietary software that implement exotic hash functions: the hash function $H$ for me is a black box, and I need to test it.

So, if the seller of the function says it is resistant, I need to check it by experiments and some statistical analysis of the experimental results.

Back to the question... If this standard exists, I am supposing that is a kind of probability definition, so,  will be someting like (is it? need only to check the number $c$ of collisions) $$Pr[H](S)=\frac{c}{|S|}=\frac{c}{s}$$

Bad hash functions (example) have characteristic values of $Pr$ that not depends only on $|S|$...  We can use  $c$ to compare the efficiency of the bad hash  with other hashes. I am imagining that  I can  use $c$ or an averaged $\overline{c}$ based on many $c_i$ tests as a metric of collision rates.

NOTES

Let $c_1$ the number of collisions in $H_1(S)$ and  $c_2$ the number of collisions in $H_2(S)$, them we can compare the two hash functions.

To avoid bias we can do an average about many sample sets $S_1$, $S_2$, etc. So there are averaged $\overline{c}_1$ and  $\overline{c}_2$ as good estimators.

Theoretically we can also estimate the minimum $\overline{c}$ of a hash function with digests of $k$ bits by   $${Pr}_{min}[H](S) ~=~  1 - \frac{2^k!}{(2^k)^s (2^k - s)!} ~\approx~ 1 - exp({-s^2/2^{k + 1}})$$

Conclusion, a good score to compare hash functions is
$$q ~=~ Pr[H](S) - Pr_{min}[H](S) ~\approx~ \frac{\overline{c}}{s} -1+exp({-s^2/2^{k + 1}})$$

When $q=0$ we have "perfect hash function", that have an expected behaviour about collisions... Imagining that hashes like SHA1 are always perfect because is impossible to compute $\overline{c}$, but  truncated SHA1 or "bad hashes" can be tested about big $S$ samples. PS: negative $q$ is possible when  $H$ and $S$ are not independent.

My interest is the behaviour of these truncated or bad hashes, and to compare them.

There are a few standard quantities related to families of hash functions $H_k\colon \{0,1\}^m \to \{0,1\}^h$ for a uniform random key $k$.  You might call them metrics.  They came to prominence in Carter and Wegman's research program on universal hash families (paywall-free), though their first use in cryptography for one-time authenticators, by Gilbert, MacWilliams, and Sloane (paywall-free), predated the Carter–Wegman program by several years.

An upper bound on $\Pr[H_k(x) = u]$ for any $x \in \{0,1\}^m$ and $u \in \{0,1\}^h$.  If it is $1/2^h$, then we say the family is equidistributed.
An upper bound on $\Pr[H_k(x) = H_k(y)]$ for any distinct $x, y \in \{0,1\}^m$.  For example, if it's at most $1/2^h$, we say the family is universal; if it's at most $\varepsilon = O(1/2^h)$, we say it's $\varepsilon$-almost universal.  The quantity $\Pr[H_k(x) = H_k(y)]$ is sometimes called the collision probability.
An upper bound on $\Pr[H_k(x) \oplus H_k(y) = u]$ for any distinct $x, y, \in \{0,1\}^m$ and any $u \in \{0,1\}^h$.  If it's at most $\varepsilon = O(1/2^h)$, we say it's $\varepsilon$-almost xor-universal.
An upper bound on $\Pr[H_k(x) = u, H_k(y) = v]$ for any distinct $x, y \in \{0,1\}^m$ and any $u, v \in \{0,1\}^h$.  If it's at most $\varepsilon = O(1/2^{2h})$, we say it's $\varepsilon$-almost strongly universal or $\varepsilon$-almost pairwise independent.
An upper bound on $\Pr[H_k(x_1) = u_1, \dots, H_k(x_n) = u_n]$ for any distinct $x_i \in \{0,1\}^m$ and any $u_i \in \{0,1\}^h$.  If it's at most $\varepsilon = O(1/2^{nh})$, we say it's $\varepsilon$-almost $n$-independent or $n$-universal.

There are standard provable examples of functions attaining optimal or near-optimal values of the above bounds.  In cryptography, these bounds are relevant to one-time authenticators such as Poly1305 and GHASH, which are based on equidistributed $\varepsilon$-almost xor-universal hash families for $\varepsilon \approx \lceil m/128\rceil/2^{128}$, as well as to other applications such as hash tables with non-adaptive adversaries.  The quantity $\Pr[H_k(m') = a' \mathrel| H_k(m) = a]$ for $m' \ne m$ is sometimes called the forgery probability.

An $n$-independent hash family has the property that the probability of a collision $H_k(x) = H_k(y)$ for distinct $x, y \in S$ in a subset $S \subseteq \{0,1\}^m$ of $n$ elements is $$1 - \frac{2^h!}{(2^h)^n (2^h - n)!} \approx 1 - e^{-n^2/2^{h + 1}}.$$  However, the key must be enormous to guarantee this.  Further, none of these bounds guarantees anything about the difficulty of deliberately computing a collision knowing the key.

What you are probably getting at is not collision probabilities for unknown keys, but rather the collision resistance of a hash family:

An upper bound on $\Pr[x \ne y, H_k(x) = H_k(y)]$ where $(x, y) = A(k)$ and $A$ is any random algorithm.  If this negligible when the expected cost of $A$ is below $\sqrt{2^h} = 2^{h/2}$, we say the family is collision-resistant.

In particular, if $B_t(f)$ is a random algorithm that applies the birthday paradox to $t$ uniform random inputs to $f\colon \{0,1\}^m \to \{0,1\}^h$ as an oracle and returns a collision if there is one (for example, using van Oorschot and Wiener's parallel collision search machine), then for any equidistributed $f$, $$\Pr[x \ne y, f(x) = f(y)] = 1 - \frac{2^h!}{(2^h)^t (2^h - t)!} \approx 1 - e^{-t^2/2^{h + 1}},$$ where $(x, y) = B_t(f)$.  When $t^2 \lll 2^h$, so that $t \lll \sqrt{2^h} = 2^{h/2}$, this is negligible in $h$.  The best generic attack on $H_k$ with cost $t$ is $A(k) = B_t(H_k)$; if there is no known attack better than this we say that $H_k$ is collision-resistant.

We don't know how to prove this for all random algorithms $A$, however, so this property can only be conjectured of hash families for which we haven't figured out a cheaper collision search algorithm.  For example, we are quite confident that Poly1305 or GHASH is not collision-resistant; it is trivial to compute two-block collisions under any key with one field multiplication and one field addition.  We conjecture that keyed BLAKE2 is collision-resistant because nobody has figured out how to make it collide.

It is of little use to empirically study collision resistance by sampling outputs of a generic hash function.  If you try to use the generic birthday algorithm on Poly1305 or GHASH, it won't do much better than it will on keyed BLAKE2.  But it doesn't take a genius of a cryptanalyst to immediately recognize there is a trivial algorithm to find Poly1305 and GHASH collisions, given the key, much faster than the generic birthday algorithm.  The best we can do is to empirically study it by sampling algorithms for finding collisions—asking a lot of smart cryptanalysts to try to think of them.  So far, empirically, nobody has thought of a way to find collisions in keyed BLAKE2.

Since sampling outputs is not useful for studying collision resistance, when studying simplified versions of hash families, we don't normally study a progression of truncated output sizes. Rather, we structure the hash family to iterate some internal scrambling function for a variable number of rounds, and study a progression of numbers of rounds.  For example, the best known collision attacks on reduced-round versions of BLAKE apply only to 5 rounds, which is why the BLAKE2 designers felt comfortable recommending only 10 rounds.

Loosely, we sometimes also pick a fixed hash function such as SHA3-256, and say that it is collision-resistant if nobody has found a way to compute a collision under that fixed hash function.  Of course, if $h \leq m$, we are guaranteed that a collision exists, so there must exist a trivial random algorithm of negligible cost to compute it: namely an algorithm that simply returns the collision without doing any computation.

So there's no nice way to formalize this, but in practice, it seems to be hard.  Twenty years ago, it was conjectured that SHA-1 was collision-resistant in this loose sense, until someone figured out a way to compute SHA-1 collisions at lower cost than the generic attack in 2004, and then someone published an actual collision last year.  Today, it is still conjectured that SHA-256 is still collision-resistant in this loose sense.


Minimal size of share in Shamir's Sharing Scheme Why does the combined shared key in Adi Shamir's Sharing Scheme have to be smaller or equal than each secret share?

As listed by Shamir, the first property is:

(1) The size of each piece does not exceed the size of the original data.

Here's what he means; there's a public value $p$; the original data is encoded as a value between 0 and $p-1$.  In addition, the secret portion of each share ('piece')  is a value between 0 and $p-1$, hence the size of each piece does not exceed the size of the original data.

What Shamir meant is that the scheme doesn't expand the share size beyond the size of the representation of the secret.  It can be shown that if the share size is smaller than the representation of the secret, then someone with $k-1$ shares (where $k$ is the threshold) can deduce some information about the secret (at the very least, some values which the secret cannot be).  Hence, Shamir's method is optimal in this sense.


Is constructing IND-CCA2 public key encryption schemes particularly easy with the KEM/DEM approach? After the introduction of McBits, I was interested what security notions are neccessary for IND-CCA2 security of integrated encryption schemes (IES, following the key encapsulation mechanism / data encapsulation mechanism KEM/DEM  approach). Now I've recently answered a different question and stated that the DEM and the KEM both need to be CCA secure in order for the whole scheme to be CCA secure.

As a consequence of this I asked myself how to generically construct an IND-CCA2 public key encryption scheme. My question now is:

Is the below ("simple") KEM/DEM public key encryption scheme IND-CCA2 under the assumption that $KDF(x)$ behaves like a random oracle and that $f_K(m):\mathcal K\times \mathcal M \rightarrow \mathcal C$ is an invertible one-way trapdoor function?

The scheme (formalized as per "Introduction to modern Cryptgraphy", second edition, by Katz and Lindell):

The KEM:
$Gen:$ the same as for $f_K(m)$
$Encaps:$ choose a random $k\in \mathcal M$, apply $c\gets f_K(k)$, convert both to a (suitable) binary representation and output $(c,KDF(k))$ with KDF being a secure arbitrary length hash function
$Decaps:$ convert $c$ from a binary string to an element of $\mathcal C$, apply $k\gets f^{-1}_K(c)$ and output $KDF(k)$ or $\bot$ in case $k=\bot$ which is always the case whenever $c \notin \text{Range}(f_K)$ holds.

The encryption scheme is then constructed as in construction 11.10, meaning the returned $c$ is prepended to the ciphertext, the $KDF(k)$ is used to key an authenticated encryption with associated data (AEAD) scheme which does the bulk encryption. To prevent unclearities while parsing the inputs and outputs a special encoding (pairing functions) must be used, any additional data introduced here will be fed into the AEAD scheme, see this comment (by Ricky Demer) for the details. Decryption is then obviously applying Decaps to the prepended $c$ and decrypting and verifying using the AEAD scheme, decryption fails (and thereby returns $\bot$) if either $Decaps$ or the AEAD scheme return $\bot$.

If I understand the question correctly, you are asking whether it's really needed to have the KEM be CCA secure, and maybe in the random oracle model it would suffice for it to just be an invertible one-way function.

This would not be CCA2-secure. Specifically, let $f$ be any invertible one-way function, and construct $f'$ so that $f'(x)=0f(x)$ for every $x$. In addition, the inversion function works by ignoring the first bit of $y$ and then inverting the rest using $f^{-1}$. Note that $f'^{-1}(0y) = f^{-1}(1y)$ for every $y$. Thus, it is possible to change a single bit in the ciphertext, and the encrypted value remains untouched. Since the CCA2 experiment allows the adversary to query a decryption oracle on anything but the challenge ciphertext, this would allow it to obtain a decryption (by changing the appropriate bit of the ciphertext). I know that this is a stupid counterexample, but this is exactly the point of these counterexample: it demonstrates that additional properties are needed.

If we ask the same question for a trapdoor permutation then this seems more promising. The same KEM proof when using RSA (see Section 11.5.5) may go through in this case. I'm not guaranteeing it, since sometimes proofs fall on strange things, but it's my intuition. I suggest writing out a proof to make sure.


Is SSH over TLS 1.2/1.3 overkill? I am designing a protocol that will have security in mind as one of its key goals. Currently I have selected SSH with TLS as the underlying transport.

I selected SSH because it had a variety of extensible authentication methods built-in already, which would not only make it easier to add my own in the future but (in some cases) make it unnecessary to add any at all, depending on how the user wants to authenticate themselves. It also has file transfers built-in, which is a nice bonus for me too.

With that in mind, should I continue using SSH over TLS, or is that overkill? Or should I switch to using normal non-SSH-based sockets?

Side note: this protocol will not be used to access remote systems via a command terminal.

SSH over TLS isn't just an overkill, it's a software bloat / design creep.

Both protocols provides confidentiality, integrity, and authenticity guarantees, so using two is redundent. And coding for both of them would increase the size of the software, making it harder to maintain software quality, efficiency, and security.

Benefit of SSH

SSH is already a very good application data encapsulation protocol, and in fact, the most widely used SSH implementation "OpenSSH" allows you to setup your own service running side-by-side with sftp. In my opinion, SSH is easier to setup and have many desireable features for specialized application.

On the other hand TLS carries too much legacy, it has too many options that needs to be supported to maintain compatibility with existing implementations. Even if you implement no support for versions before TLS-1.3, incorporating support for it in code still require considerable amount of expertized skills.


Known methods for constant time (table-free) AES implementation using 'standard' operations? There are several known methods for implementing AES in constant time using SIMD operations, mostly based around fast byte shuffling (for instance Hamburg and Kasper/Schwabe). Are there any similar approaches that allow a constant-time AES to be implemented using only standard C operations? The closest thing I've seen is this byte oriented AES implementation, but it uses input-dependent loops to compute logarithms and exponents for the sbox.

Generally speaking, a lookup-table can be implemented in constant time by doing it as if it was a hardware circuit.

Consider a multiplexer: this is a circuit which accepts three inputs $a$, $b$ and $c$, and yields one output $d$ which is equal to $a$ if $c = 0$, to $b$ otherwise (I am talking about single-bit values here). A multiplexer can be used to implement a $1\rightarrow1$ lookup table: set $a$ to the value of the table for a "0" input, $b$ to the value for a "1" input, and set $c$ to the actual input you want to transform.

If you store single bit values in variables, the corresponding C code looks like:

d = (a & ~c) | (b & c);

which has a constant execution time.

If you know how to implement $n\rightarrow1$ lookup tables with constant-time code, a $n+1\rightarrow1$ lookup table is obtained by isolating the last bit: you consider the two $n\rightarrow1$ sub-tables, the first one being the table you get by setting the last bit to 0 or 1, respectively. Then you use the outputs of those two sub-tables as $a$ and $b$ inputs for an extra multiplexer controlled by the last input bit. This means that a $n+1\rightarrow1$ table is just a pair of $n\rightarrow1$ tables and extra bit which decides which of the two tables we were actually talking about.

With this construction, a $8\rightarrow1$ table is implementable as a tree of 255 multiplexers like the one above. The AES S-box is an $8\rightarrow8$ table, and is applied to 16 values in parallel at each round, so you end up to having to evaluate $128\times255$ multiplexers per round.

However, with the C code above, you are actually computing several multiplexers in parallel. If the C variables are 64-bit values, then you are doing 64 multiplexers simultaneously: bits of index 0 talk to other bits of index 0, bits on index 1 with bits of index 1, and so on, up to bits of index 63. This is known as bit slicing. Due to the similarity of structure in AES, you can use that to reduce the number of multiplexer evaluations to $4\times 255$ per round: a mere thousand...

With such techniques, you can end up with a constant-time, plain C implementation of AES which should evaluate a block in, say, 20000 clock cycles. Which is awfully slow, but still doable. However, this is only the beginning. There are many optimizations which can be applied to such a structure (e.g. you can replace multiplexers with a not-exactly-a-multiplexer construction "a ^ (b & c)", which selects between $a$ and $a \oplus b$ ($a$ xor $b$), and is enough to implement a lookup table; also, the first row of multiplexers in a tree can often be collapsed since its inputs are known values of 0 or 1). For the DES S-boxes (eight distinct $6\rightarrow4$ tables), very optimized bitsliced implementations were designed by Matthew Kwan back in 1998. Moreover, the AES S-box has an internal algebraic structure which can probably be further exploited.

A google search on "bitslice implementation AES" links to a few research papers, but apparently none being publicly downloadable.


Encryption algorithm used in WPA/WPA2 I want to know how EXACTLY the WPA password gets encrypted

I have been searching through and I was able to catch:

The actual password is converted to some hash
Salting is applied to the hash
The operation is not reversible
The hash comes with the 4-way handshake

So what kind of hash is it converted? like, SHA1? MD5? and how the salting process is done? like, is the SSID appended to the password before the hashing operation?

Or maybe I have some misunderstanding here?

A key is derived from the password using a Password Based Key Derivation Function, in this case PBKDF2:

Key = PBKDF2(HMAC−SHA1, passphrase, ssid, 4096, 256)

PBKDF2 in turn is described by PKCS#5. These RSA cryptographic standards in turn are made available through RFC's nowadays, in this case RFC 2898: PKCS #5: Password-Based Cryptography Specification Version 2.0.

In this case the password needs to be 8 to 63 characters in size. The characters are converted to binary using ASCII so you can only use characters in the (printable) character range of ASCII.

In PBKDF2 the binary password is used as key to the HMAC function. The salt is the SSID of the Wi-Fi connection. The salt + a counter value is used as the initial input to the HMAC function. After that the previous HMAC output is used as input, until 4096 HMAC rounds is reached. Unfortunately it seems that it outputs 256 bits while SHA-1 only output 160 bits. This means that you have to increase the counter once and do all the rounds all over again.

The output of the PBKDF2 function is the pre-shared key or PSK. The PSK is used directly as PMK (pairwise master key) in the 4-way handshake.

This is also described in section H.4 : Suggested pass-phrase-to-PSK mapping of IEEE 802.11i (2004) which is available for download from the IEEE web site.


Signature generation using hash function I want to generate a valid signature for a message using the below algorithms:

Hash function: $H(x) = (x+3) \bmod 10$
(I am unable to understand the given parameter for hash function and how am I supposed to use it in hashing a message.)

Encryption: RSA with the following parameters

Private key: 11
Public key: 5
Modulus: 14
(I had tried but failed in using these parameters in RSA encryption. I want to know the possible way or hint to be able to use these exponents in encrypting the hash of a message.)

The private key is actually the private exponent. Signature generation is modular exponentiation using the private exponent and - of course - the modulus. So you first hash a value for x using the hash function, giving you another value, say $h$. Now you perform the modular exponentiation on it and return the result. And that's all there is to it.
Note that you should not perform modular exponentiation by first perform exponentiation and then take the modulus: you can use the modulus in the intermediate steps (e.g. multiplication).
Do not think of signature generation as encryption with the private key. It only is similar in for textbook RSA, but otherwise that kind of comparison only hampers understanding of signature generation.


How do RSA and ECDSA differ in signing performance? Signature algorithms with elliptic curves have smaller output sizes compared to RSA for the same level of security.

What about the processing time to generate a signature ?

I've seen figures giving the advantage to RSA. That seems curious.

Leaving aside the implementation aspects, what could justify (in terms of number of operations) the fact that ECDSA produces signatures faster than RSA (or vice versa) ?

ECDSA should in general create signatures faster than RSA for the same cryptographic strength if you just look at the mathematics. In the end the modular exponentiation is performed for smaller numbers. However, ECDSA depends on a random number generator, so ECDSA speeds may be slower if the random number generator blocks for any reason (and not using a good random number generator may compromise the ECDSA private key). The RSA PSS signature scheme also requires the use of random numbers, negating this performance advantage for RSA for this particular padding scheme.

[EDIT: well, the use of a random salt in RSA / PSS is at least the default option, and many implementations won't allow you to use an empty salt to make the scheme deterministic. RSA / PKCS#1 v1.5 padding for signature generation is fully deterministic and could be used instead; it doesn't come with a security proof like PSS does, but it hasn't been broken either]

RSA is generally much faster for signature verification as verification is performed using the public key. If a small exponents such as F4 (65537 or 10001 in hexadecimals) are used then RSA is generally faster than ECDSA, as only a minimum of modular multiplications is necessary.

The time required for RSA operations with the private key quickly rises for larger security strengths. ECDSA times also rise, but at a much slower rate.

ECC is much much faster than RSA for key generation. Finding large primes for RSA is a tough job even for current CPU's given a high enough key size.

Most RSA libraries have been around for a long time, are used much more often and are therefore more likely to have been optimized. So an RSA implementation may be faster than an equivalent ECDSA implementation (for small key sizes). ECC, in general, is a more complex algorithm to implement - but not necessarily to optimize, as CodesInChaos points out below.

Anyway, real world results will rely heavily on the speed of the implementations used. Note that the security level of such libraries also differs wildly, and selecting a crypto library just based on performance is not a good idea.


Public key encryption and decryption with private key I am learning cryptography and here is what I understood so far:

  Story. I decide to talk with my friend over unencrypted channel. We
  exchange public keys with each other so that we can encrypt text files (messages). Once other party encrypts the message with my public key (the public key I given to my friend) and sends that encrypted file to me, I can decrypt message with my private key.

Here is how I create my key pair.

openssl genpkey -out privkey.pem -algorithm rsa -pkeyopt rsa_keygen_bits:4096
openssl pkey -pubout -in privkey.pem -out pubkey.pub

Then I can give this pubkey.pub to my friend who can encrypt message for me and send ecrypted file to me. I try this myself:

openssl enc -e -aes-256-cbc -in text.txt -out message.xxx -pass file:./pubkey.pub

This worked OK, I created encrypred file. But I cannot decrypt it:

openssl enc -d -aes-256-cbc -in message.xxx -out decrypted.txt -pass file:./privkey.pem

bad decrypt
139927387231896:error:06065064:digital envelope routines:EVP_DecryptFinal_ex:bad decrypt:evp_enc.c:529:

I could decrypt with pub key but that is not what I was trying to achieve. What I would like to is implement simple practical example of Alice and Bob https://en.wikipedia.org/wiki/Public-key_cryptography It is all clear and easy in theory, but I could not find any easy and clear practical example like mine.

Added, list of files:

ls -alh
total 28K
drwxrwxr-x  2 user user 4.0K Sep 21 17:59 .
drwxrwxr-x 11 user user 4.0K Sep 21 16:08 ..
-rw-rw-r--  1 user user   64 Sep 21 17:59 decrypted.txt
-rw-rw-r--  1 user user   96 Sep 21 17:58 message.xxx
-rw-rw-r--  1 user user 3.2K Sep 21 17:08 privkey.pem
-rw-rw-r--  1 user user  800 Sep 21 17:08 pubkey.pub
-rw-rw-r--  1 user user   74 Sep 21 17:58 text.txt

You are trying to encrypt and decrypt with AES, which is a symmetric algorithm, using your RSA keys (which are meant to work with RSA, which is an asymmetric algorithm).

To use AES, both sides need to know the same secret key - there aren't separate public and private keys. The way you would usually do this is to choose a random secret key for AES (often called a data encryption key or DEK), encrypt the file using that key and the AES algorithm, then use RSA to encrypt that DEK using your friend's public key. You would give your friend both the encrypted document and the encrypted DEK. She would decrypt the DEK first using her RSA private key, then use the recovered DEK to decrypt the document. This technique is commonly called envelope encryption.


Questions about indexing a hash output to compose a final key Recently I have watched the video Multi-Precision Arithmetic for Cryptology in C++, at Run-Time and at Compile-Time (at 21:56 seg) :

The speaker says that to use a byte from the user key as a subscript of an array allows side channel attacks. My question is what if to use this during a key crunching stage:

Do

   HashOut = DoHash()

   FinalKey += HashOut[currentKeyByte mod KeySize]

   currentKeySize += 1

While (Len(FinalKey) < WantedSized);

Let's forget for a minute the widely known KDFs, okay? The idea behind the pseudo-code above would interfere in constant-time aspects?

If it does. What if to use the bytes from hashed key instead of the original bytes of the key?

Thanks in advance!

The speaker says that to use a byte from the user key as a subscript of an array allows side channel attacks.

Using secret data (be it the user key, the actual secret key or internal key or secret-dependent data of the crypto routine) can, depending on what you're doing and what sort of access the attacker has to your machine while you're working with the key.

  My question is what if to use this during a key crunching stage

  FinalKey += HashOut[currentKeyByte mod KeySize]

It depends on what currentKeyByte is (your pseudocode doesn't specify it).

If it's an index that iterates between 0 and WantedSize in a predictable fashion, then that's not an issue.  The attacker could potentially deduce information of what currentKeyByte is; on the other hand, if he knows that this is iteration 5, he already knows that currentKeyByte is 4, and so any further information he gets from the side channel doesn't tell him anything he doesn't already know.  Now, if that's the case, then this code would wrap around if KeySize < WantedSize; that's might not be what you want to do, but that's an unrelated issue.

On the other hand, if currentKeyByte is, in fact, a byte from the user's password, well, yes, that can be an issue (if the attacker can plausibly run a program on the same computer while the above code is running); if I were you, I'd rethink this, and rework this code.


Is there a TLS extension for generating unique IVs for AES GCM? Since reusing IVs is death for AES GCM, it seems like using the fixed IV in the TLS connection state is a phenomenally bad idea. It wouldn't even seem to be a good idea to use the salt + counter method since an attacker could watch for the first ciphertext record exchange and keep track from there. Is there an extension to address this? The RFC is distinctly unhelpful.

You can check this answer which mentions how does the IV generated for GCM ciphers in TLS 1.2

  ... is an AEAD Cipher, so it is in the form of GenericAEADCipher:

struct {
     opaque nonce_explicit[SecurityParameters.record_iv_length];
     aead-ciphered struct {
         opaque content[TLSCompressed.length];
     };
  } GenericAEADCipher;

  Here, the nonce_explicit contains 8 byte nonce, and you combine this
  with the 'fixed IV' from key derivation (4 bytes) then you get 12 byte
  IV for AES-GCM mode encryption. (Note that you only sent the
  last 8 bytes of
  the IV).

Also, from the RFC 5288 (AES Galois Counter Mode (GCM) Cipher Suites for TLS)

  6.1.  Counter Reuse

  AES-GCM security requires that the counter is never reused.  The IV
  construction in Section 3 is designed to prevent counter reuse.

From Section 3 of the RFC 5288:

  The "nonce" SHALL be 12 bytes long consisting    of two parts as
  follows: (this is an example of a "partially    explicit" nonce; see
  Section 3.2.1 in [RFC5116]).

struct {
     opaque salt[4];
     opaque nonce_explicit[8];
} GCMNonce;

  The salt is the "implicit" part of the nonce and is not sent in the
  packet. Instead, the salt is generated as part of the handshake
  process: it is either the client_write_IV (when the client is sending)
  or the server_write_IV (when the server is sending).  The salt length
  (SecurityParameters.fixed_iv_length) is 4 octets.

  The nonce_explicit is the "explicit" part of the nonce. It is
  chosen by the sender and is carried in each TLS record in the
  GenericAEADCipher.nonce_explicit field. The nonce_explicit length
  (SecurityParameters.record_iv_length) is 8 octets.

  Each value of the nonce_explicit MUST be distinct for each distinct
  invocation of the GCM encrypt function for any fixed key. Failure to
  meet this uniqueness requirement can significantly degrade security.
  The nonce_explicit MAY be the 64-bit sequence number.

So, reusing the same IV in GCM ciphersuites in TLS is prevented in this way.


How can I get VMAC Code in pure c? I had find a paper about VMAC algorithm:VMAC: Message Authentication Code using Universal Hashing.

Now I want to implement this algorithm, But i don't find test vectors about it.

Who can give some advise? Where can i find it's code ?

VMAC was a joint work by Wei Dai and Ted Krovetz. It so happens that Wei Dai at that time was also actively working on his own cryptographic library (Crypto++), which of course also includes VMAC.

You can find the test vectors here and the optimized implementation here.

Two examples for VMAC-AES-128 are:

Key: "abcdefghijklmnop"
IV: "bcdefghi"

Message: ""
MAC: 472766C70F74ED23481D6D7DE4E80DAC
Message: "abc"
MAC: 4EE815A06A1D71EDD36FC75D51188A42


What happens if we choose the random secret keys in Diffie-Hellman greater than prime? Diffie-Hellman works as follows:

Given public parameters $p$ (a large prime) and $g$ (always referred to as a generator of $(\mathbb{Z}^∗_p)$. Then:

Alice randomly chooses $a<p$ and sends $A\leftarrow g^a \mod p$ to Bob;
Bob randomly chooses $b<p$ and sends $B\leftarrow g^b \mod p $ to Alice;
Alice computes $S\leftarrow B^a \mod p$;
Bob computes $S\leftarrow A^b \mod p$.

What happens if we choose $a$ and $b$ grater than $p$?

The modulus operation $\pmod p$ is performed at each step and reduces the result into $\bmod p$. And a clever implementation can use the Fermat's Little Theorem instead of taking the power than reducing to modulo $p$. After that it's possible to use the modular version of repeated squares algorithm or similar.

Example 1) code used from  sublimerobots

sharedPrime = 23    # p
sharedBase = 5      # g

aliceSecret = 600     # a
bobSecret = 1500      # b

Alice Sends Over Public Chanel:  8
Bob Sends Over Public Chanel:  4

Privately Calculated Shared Secret:
Alice Shared Secret:  2
Bob Shared Secret:  2

Example 2)

sharedPrime = 23    # p
sharedBase = 5      # g

aliceSecret = 6000000     # a
bobSecret = 15000000   # b

Alice Sends Over Public Chanel:  8
Bob Sends Over Public Chanel:  4

Privately Calculated Shared Secret:
Alice Shared Secret:  2
Bob Shared Secret:  2

I think you are confusing the mathematical representation and the actual value.

In the sense of optimization, the code from sublimerobots is not good. Actually. instead of

bobSharedSecret = (A**bobSecret) % sharedPrime

a faster version

bobSharedSecret = pow(A,bobSecret,sharedPrime)

which uses modular binary exponentiation.


Oblivious transfer variation question Now I am doing a variation of the oblivious transfer, I have to use 2 people, pebbles, and boxes. I need to find out if who has a larger number between Alice and Bob (variation of Yao's Millionaires' Problem). This is what I have come up with:

Bob enters a room where alone where 100 boxes are and he inserts a pebble in the n_Bth box.
Alice enters the room alone where the boxes are and she inserts a pebble in the n_Ath box and a pebble into each $(n_A+1)$th box till she reaches the last box ($100$th box). She cannot shake any of the boxes because the noise will be heard by Bob who is waiting outside.
Bob enters the room and he changes the order of the boxes. He cannot shake the boxes for the same reason.
Alice enters the room and she changes the order of the boxes. She cannot shake the boxes for the same reason.
Now Alice and Bob both enter the room and they shake each box. If they hear $2$ pebbles in one box, it means that $n_A < n_B$. Alice now only knows that $n_B$ has to be larger than her number. If a box does not contain two pebbles then $n_A > n_B$. Alice now only knows that $n_B$ is less than her number.

Now the only problem is, that it only works if Bob has a larger number than Alice. If Alice has a larger number than Bob, then none of the boxes will have $2$ pebbles and they will both know that Bob's number is larger than Alice. However, Bob has an advantage as to figuring out what number Alice has, because Alice put pebbles in her box and all boxes greater.

Example using 10 boxes:

 Alice's number = 7, Bob's number = 3

 x    x   x   x               x
 10   9   8   7   6   5   4   3   2   1

 After the randomization process, Alice and Bob both know that Alice's number is
 larger than Bob's. But the Prob(of b = 4 or 5 or 6) = 0% because all Bob has to do
 is subtract the number of boxes with a pebble in it from the number of boxes
 (10 - 4 (it's because he put a pebble in his box)) and he knows that Alice's number
 has to be 10, 9, 8, or 7.

If you don't follow, I can try to make it more clear.

Actually, it does not matter if Bobs number is greater or less than Alices number. In either case Bob can compute $n_A$ (here I denote by $n_A$ and $n_B$ the private numbers of Alice and Bob respectively). Bob could simply note the number of boxes with one pebbles in them and the number of boxes with two pebbles in them, lets call these numbers $p_1$ and $p_2$ respectively. Also lets by $N$ denote the total number of boxes. If $p_2 = 0$ then $p_1 = N - (n_A - 1) + 1$, and if $p_2 = 1$ then $p_1 = N - (n_A - 1) - 1$ . In general we can write this as $p_1 = N - (n_A - 1) + (1 -2p_2)$. If we rewrite this we get $n_A = N + 2(1 - p_2) - p_1$. So you see, regardless of the relation between $n_A$ and $n_B$ Bob can compute $n_A$.

You could solve this by simply not letting Bob shake any boxes, so that he never learns $p_1$ or $p_2$. I.e., in the last step instead of Alice and Bob shaking every box, you should just send Alice into the room to shake all the boxes. She will then learn the result, and can tell the result to Bob. In fact, in this case Alice does not have to shuffle the boxes, only Bob needs to do that.

You could argue that in this case Alice may cheat and tell Bob an incorrect result. However, you are already trusting Alice to follow the protocol in the previous steps, so this shouldn't be a problem.

Note, that if a box contains two pebbles it means that $n_A \leq n_B$, not $n_A < n_B$ as you state.


Password-based cipher with fast encryption Define a password-based cipher as a cipher which decryption key is a humanly memorable password, thus optimistically at most 28 to 44 bits of entropy (per the obligatory XKCD).

For a password-based cipher to have any practical security, decryption is bound to be slow (and encryption adjusted to keep decryption slow as technical progress makes password search faster). The traditional way to do this is using an appropriately parametrized entropy-stretching password-based key derivation function (such as PBKDF2, bcrypt, scrypt, or Argon2) to transform the password (and perhaps a random salt) into the key of a normal cipher. That's done for both encryption and decryption, making the two about as slow.

What are recommendable (and preferably common or/and standardized) password-based ciphers with fast encryption ?

One option would be a $(\text{password},\text{plaintext})\mapsto\text{ciphertext}$ that is fast, while $(\text{password},\text{ciphertext})\mapsto\text{plaintext}$ remains about as difficult as in traditional password-based cipher for a comparable level of security. There are other options, and I do not want to be too directive, to see what good ideas emerge.

One approach that you might consider is a puzzle; this is something where the decryptor must do some searching to find the result.

Here is one simple example: suppose the encryptor takes the password, and selects $N$ random bits; he concatenates the two and SHA-256 hashes the result.  He then takes the first 128 bits of the hash, places that in the ciphertext, and then uses the other 128 bits to AES encrypt the secret; that's the rest of the ciphertext.

He then discards the original $N$ bits he selected.

To decrypt this, we have to search for the $N$ random bits that were selected; to do that, we have to compute an average of $2^{N-1}$ hashes, which is fairly slow.  Once we have selected the correct set of random bits, it's easy to recognize it (by comparing that hash with the initial part of the hash in the ciphertext); we can then decrypt the message.

You can select $N$ to taste; perhaps 24 if you want decryption to take maybe a second; perhaps 32 if you want to make it more expensive.

There are tweaks you can do to this approach:

Use multiple levels of puzzles, to reduce the chance that decryption might be done quickly (by stumbling on the answer early)
Use something other than SHA-256 (which is fairly GPU friendly).

However, I don't see how this approach could be made that resistant to a large multi-CPU attack...

If it is important to mimimize the variation in the decryption time, one idea would be to arrange the puzzles in parallel rather than serial.  That is, we select $k$ distinct random values of $n$ bits each, and compute the $k$ values:

$$h_i = \text{Hash}( \text{Password} || r_i )$$

and expose $z$ bits of each (for some $z$ somewhat larger than $n$).

Then, we compute a final hash $\text{Hash}( h_0, h_1, ..., h_{k-1}$, expose 128 bits of that (and use the other 128 bits as the actual key).

To decrypt, someone would need to compute $\text{Hash}( \text{Password} || x )$ for various values of $x$, and see if that matches any of the partially revealed $h_i$ values.  The decrypter will need all $k$ of them, and hence will need to try almost all $2^n$ possible values of $x$.

As an example, for $\text{Hash} = \text{SHA-256}$, $n = 28$ (a single for of my test machine can perform $2^{28}$ SHA-256 hashes per minute), $z=32$ and $k = 10$, then this would yield a decryption with about 10% variation, with 56 bytes of overhead...


Block cipher mode of operation with beyond-birthday-bound security I am looking for block cipher modes of operation that are secure even when the number of blocks encrypted exceeds the birthday bound.

It is not a standard mode of operation and I do not know if anyone uses it in practice, but one option is double encryption using counter mode and a non-repeating counter. That is, doing $E_{k_1}(i) \oplus E_{k_2}(i) \oplus p$. The sum of two PRPs is a PRF with better bounds than one. The bound is basically $O(2^{2n/3})$  rather than $O(2^{n/2})$. See The Sum of Two PRPs is a secure PRF.

For example, with a 64-bit block size that means something like going from encrypting 32 gigabytes before attacker advantage to encrypting 32 terabytes instead.


Is this DIY remote lock protocol secure? I need your advice on following scheme of exchange protocol between remote lock and key. I'm planning to use following algorithm:

Key generates unique value that never repeats (in reality it's just counter that increments every time the button is pressed), let's call it "NONCE1".
Key sends a request to the lock which consists of NONCE1 and H1 = MD5(NONCE1 + KEY1). Second part is used only for "signing" the request, attacker wouldn't be able to generate valid request if he doesn't know KEY1.
Lock checks if H1 = MD5(NONCE1 + KEY1), this is used to check if incoming request is coming from the key (or at least from the one who is aware of the value of KEY1). Additional steps that were not described previously is:

Lock checks if NONCE1 of the previous key request less than NONCE1 received just now. This part prevents acting on previously processed requests, attacker who has such request won't be able to go any further. I'm trying to leave him in the situation where old requests are not accepted by the lock, and new requests couldn't be generated because he can't reproduce it without KEY1.
Lock sets NONCE1(previous request) = NONCE1(current request)

Lock generates completely unique value that never repeats, let's call it "NONCE2".
Lock sends a response to the key which consists of H2 = MD5(NONCE2 + KEY2). NONCE2 - is counter based (in order to completely exclude possible collisions), so in order to hide it's "counter - based nature" from an attacker, MD5(NONCE2 + KEY2) is used here.
Key does H3 = MD5(H2 + KEY3) and sends it back to the lock
Lock checks if H3 = MD5(H2 + KEY3) and acts on that

What could be possible vulnerabilities? Is it safe enough to use MD5 in this particular case?

I've added some additional "substeps" to clarify it a little bit

Accepted suggestion / solution is following:

Get rid of steps 1 - 3
Replace MD5 with HMAC-XXX

Even after your updates, the first part seems unnecessary. However, steps 4-5 do indeed prevent the attacker from learning future nonces they could ask the key MAC values for. So the protocol steps 4-7 would be secure with a secure MAC.

I agree with CodesInChaos that using HMAC would be better, because H(m||k) has some weaknesses, while HMAC is standard. Unless you have a good reason to use MD5, I would also prefer to use a stronger hash, though HMAC-MD5 is still secure (that is about encrypted data, but applies generally).

However, I do not think the weaknesses actually apply here, since the attacker does not have freedom to choose the values they need to calculate the keyed hash for. So even as is it should be secure. Despite that I would recommend switching to HMAC. Even better would be to use an existing mutual authentication protocol meant for this purpose, like the one descrived in Chapter 10 of HAC (see 10.2.3).

The below applies to the protocol as described in the original version of the question.

  Key generates completely unique value that never repeats (some kind of a counter), let's call it "NONCE1".
  Key sends a request to the lock which consists of NONCE1 and H1 = MD5(NONCE1 + KEY1)
  Lock checks if H1 = MD5(NONCE1 + KEY1)

This part does not prove anything to anyone, so it is useless. An attacker who impersonates the key can reuse any previous nonce+MD5-pair because the lock does not know if the nonce is unique. An attacker who impersonates the lock can simply ignore the data received.

  Lock generates completely unique value that never repeats, let's call it "NONCE2".
  Lock sends a response to the key which consists of H2 = MD5(NONCE2 + KEY2)

Why not simply send NONCE2 to use as H2? The hash does not seem to help in any way, because the nonce is not used for anything else.

  Key does H3 = MD5(H2 + KEY3) and sends it back to the lock
  Lock checks if H3 = MD5(H2 + KEY3) and acts on that

This is the only part of the protocol that has a clear purpose: the lock is verifying an ad-hoc MAC to authenticate the key.


open source whitebox-crypto implementation I am trying to code a simple WBC situation to help my understanding about white-box cryptography.

Details:

I have 2 programs, a "server" and a "client", the server utilises caesar cipher (key = 2) encrypts the plaintext "HELLOWORLD" and sends it to the client.
On the client side, key = 2 is embedded into the source code.

how would the WBC implementation of either my "server" or "client" be different from a normal "server" and "client"

The current way of implementing a (symmetric) cryptographic algorithm as a white-box is to implement it as a network of encoded lookup tables (a good white-box will also have so called 'external encodings' applied, but I'll skip these for now).

In this case however, a network of tables is not required (one table will do) and as a result encoding the tables is no longer nescessry.
So in this case, I would implement this algorithm as 'a lookup table'.

Let's say (for easyness) that A=0, B=1, ..., Z=25.
Than we can implement the decrypt function on the client as following:

public int WhiteBoxDecrypt(int letter) {
    // Decrypt one encrypted block - in this case, a block is one character (represented as integer).
    int[] lookupTable = {24, 25, 0, 1, 2, ..., 23 };
    return lookupTable[letter];
}

Note that this implementation is as secure as a black box implementation would be (well, a black-box implementation that would decrypt per character). The only way to crack this implementation is to compare the inputs and outputs to the algorithm (all of these inputs and outputs are provided in a single table).
This is why using lookup tables is so cool - it's a datastructure that shows just inputs and outputs, just like a real black-box would do.

Bonus: a pretty good tutorial by James Muir on implementing a white-box AES can be found here.


Proving knowledge of a preimage of a hash without disclosing it? We consider a public hash function $H$, assumed collision-resistant and preimage-resistant (for both first and second preimage), similar in construction to SHA-1 or SHA-256.
Alice discloses a value $h$, claiming that she (or/and parties she can communicate with or/and devices they have access to) knows a message $m$ such that $H(m)=h$. Can some protocol convince Bob of this claim without help of a third party/device that Bob trusts, nor allowing Bob to find $m$?
At Crypto 98 rump session, Hal Finney made a 7-minutes presentation A zero-knowledge proof of possession of a pre-image of a SHA-1 hash which seems to be intended for that. This remarkable result is occasionally stated as fact, including recently here and next door. But I do not get how it is supposed to work.
Update: This talk mentions using the protocol in the Crypto'98 paper of Ronald Cramer and
Ivan B. Damgård: Zero-Knowledge Proofs for Finite Field Arithmetic or: Can Zero-Knowledge be for Free? (this version is very similar, or there is this earlier, longer version).

I'm not sure what I can add that wasn't covered in the talk. The approach is that Alice commits to the preimage and sends the commitment to Bob. The commitment has homomorphic properties, meaning it is possible to do computation on the value.

For example, if Alice commits to $x$ and $y$, Bob may be able to compute a commitment to $z$ where $z=f(x,y)$ for some function $f$. For example, if the commitments are additively homomorphic, Bob can add two commitments or multiply by a constant for free.

Alternatively, $f$ may not be directly computable. In this case, Alice who knows the actual values computes $z$, sends a commitment to $z$ to Bob asserting that it is correct. Bob holds commitments to $x$, $y$, and $z$; as well as knowing $f$. Alice can then interactively prove that for $f$, the commitment containing $z$ does contain the correct output for the inputs contained in the commitments to $x$ and $y$.

The Cramer-Damgaard paper shows how to do these proofs for a simple Turning-complete set of both boolean and arithmetic gates (for example, NAND and modular addition/multiplication).

The size of the circuit implementing SHA-1, expressed with only NAND gates for example, will be very large and infeasible. The art to doing the proof in practice is breaking it into subprotocols that are best represented by either boolean or arithmetic circuits and switching between the proof systems as appropriate. For certain SHA operations, he works at the bit level with boolean operations and for other operations, he works with integers in a finite field.


Using states of a double pendulum as a one-way function Hello,

as a non-professional (at all) but a fan of cryptography, I have one idea and I would love to hear your input on it.

As I understand cryptographic functions they should have following attributes:

from private to public part - fast and easy
from public to private - hard

Ok, thats the basis premises I will try to follow.

This works for RSA and elliptic curves and so on... If I understand it right.

Now to the idea:

I have checked a documentary on double pendulum and chaos theory and I find it a very nice idea so I thought like, why not using similar one?

For some details on double pendulum examples see:
http://www.tapdancinggoats.com/double-pendulum

Ok as output there would be the states of pendulums after simulation.

And as for input there would be initial: position, amount, mass of the pendulums and length of the simulation.

It should not be a problem of simulation the process with initial data, but there should be a problem on finding the correct initial state.

What do you think? Is this idea worth looking into? :)

Thank you

Oliver

It's an interesting idea, but I don't think it offers any advantages over current one-way function candidates and may be worse. For one thing, specifying the initial data of the simulation specifies a lot of properties of the dynamical system that will remain invariant (conservation of energy, horizontal component of momentum, et cetera). There are also constraints on the phase space of the coupled pendulums that never change over time either. I'd want the scheme to not have lots of internal constraints and symmetries for an adversary to exploit.

With a dynamical system like this, assuming the adversary can just look at the pendulums, she could just "look at the internals" of your scheme at any time, set up her own Lagrangian or Hamiltonian. By just observing the motion, the state of your one-way function is "leaked".

Also, since floating-point numbers are involved in the numerical solution of the system of equations, if you and I use slightly different numerical integrators, even for the same initial state, we may get different final states / "public keys" due to rounding or Runge-Kutta methods. In fact, you will have to specify the initial position and momentum extremely well, since any small changes in this data will cause wildly different subsequent states: chaos in a nutshell.


ElGamal encryption and signature using same keys In ElGamal scheme we have message $M$; $p$, $g$ and $y=g^x \bmod p$ as public key where $x$ is unknown private key.
Encrypted message $(c,d)$, where $c=g^k \bmod p$ and $d=M \cdot y^k \bmod p$.
Signature $(r,s)$, where $r=g^k \bmod p$ and $s=(M - xr)\cdot k^{-1} \bmod p-1$

If $c=r$ then message encrypted and signed with the same $k$.
Is there a possibility to obtain private key $x$?

Is there a possibility to obtain private key $x$?

No; here's the proof.

Suppose we had a black box that, given $c = g^k, d = M \cdot y^k, r = g^k$ and $s = (M - xr) \cdot k^{-1} \bmod p-1$ (and we'll throw in $M$, and $z : y = g^z$), is able to give us $x$.

Then, here's how we can find the private key given an ElGamal signature.

We have $M, r = g^k$ and $s = (M - xr) \cdot k^{-1} \bmod p-1$ (as that's the ElGamal signature and message being signed).

That also gives us $c$.  To get $d$, we select a random $z$ and compute $d = M \cdot c^z = M \cdot y^k$.

We now have everything the Oracle expects; we pass in everything, and we recover $x$.

As we believe that deriving the ElGamal private key from a signature is infeasible, we believe there cannot be such a black box.


Which one is correct probability formula for the same master secret value in identity-based encryption Assume two servers $(n=2)$ use the same domain curve parameters and same hash function $H:\{0,1\}^{*} \rightarrow G_{1}$ . Then the hash value for the same identity falls in same result and let it be P by assuming $P \in G_{1}$. Then the probability for the same private key depends on secret value $a,b \leftarrow Z_{q}$ where q is a large prime number and (a) and (b) be the master secret value of two servers. In this scenario, the probability of $(a=b)$ can be $\frac{1}{q}$ or calculated using birthday problem?
In elliptic curve with field order 512 bits, then q=170 bits
According to simple probability
$p(n)=\frac{1}{q}=\frac{1}{2^{170}}$, the probability does not depend on $(n)$.

According to birthday problem,
 $p(n)=1-\frac{q!}{q^{n}(q-n)!}$
substituting value for (n=2) (q=$2^{170}$), then the probability will be 0.1.
Which one is correct?

Both are correct, you've just made an error calculating it.

Here is a simplification from my answer here:

$$\begin{eqnarray}
p(n) & = & 1 - \frac{q!}{q^n\left(q-n\right)!}\\
& = & 1 - \frac{\prod^q_{i=q-n+1}i}{q^n}\\
& = & 1 - \prod^q_{i=q-n+1}\frac{i}{q}
\end{eqnarray}$$

So,

$$\begin{eqnarray}
p(2) & = & 1 - \prod^q_{i=q-2+1}\frac{i}{q} \\
 & = & 1 - \prod^q_{i=q-1}\frac{i}{q} \\
 & = & 1 - \frac{q-1}{q}\cdot \frac{q}{q} \\
 & = & 1 - \frac{q-1}{q} \\
 & = & 1 - (\frac{q}{q} - \frac{1}{q}) \\
 & = & \frac{1}{q} \approx 0.
\end{eqnarray}$$


How does one use AES block cipher modes of operation? This is the sequel to my previous question about AES block cipher modes of operation.

(See: AES block cipher modes of operation)

Now, here is my real problem. I have to use a block cipher with 8 bit input block size. As you say, I think that every clock cycle I receive 128 bits of information. With the 8 bit component, I have to make a structure of 16 of these components to encrypt the 128 bit information. How many round cycles does a structure like this need to encrypt the whole 128 bits. I assume the answer is 16*10, when I choose a mode which can't be parallelized (like OFB or CFB), and just 10, when I use parallelized modes (CTR). But, in the next clock cycle, I'll receive another 128 bit of information (a new message?).

The structure which encrypts the first 128 bits, after how many round cycles can it start to encrypt a new message?
If I want to encrypt continuous information, to encrypt every 128 bit of information I receive per cycle, do I have to make as many structures, like this one described above, as round cycles of the first structure?
If I use for example CFB or OFB mode, which need an IV, I have to generate a new IV every new message (every 128 bits). Am I right?

Your question is pretty confusingly written, but let me try to make some sense of it.

You say you receive 8 bits of input every cycle.  You want to encrypt the input using AES, which operates on 128 bits at a time.  This means that you need to buffer the input somehow (a shift register might be handy here) for 128 / 8 = 16 clock cycles, until you've accumulated a full buffer to encrypt.

Conveniently, while you're accumulating the next input block, you can encrypt the previous block at the same time.  If you can do one full AES round per cycle (which apparently is indeed possible, if you can afford the gates), then you should have plenty of time to finish the encryption before the next block comes in.

Presumably, you also need to buffer the output in another shift register, and shift it out 8 bits at a time, but you can also do that in parallel with the input buffering and the encryption.  So, at any given moment, your circuit will be doing three things: reading in the next 128-bit block, encrypting the current block and writing out the previously encrypted block.

All that's assuming that you want to implement the raw block cipher, i.e. "ECB mode".  (The "scare quotes" are there because ECB isn't really a proper mode of operation suitable for securely encrypting long messages.  It's really only good as a building block for implementing other modes, but it's pretty useful for that.)  Once you have an ECB implementation, you can easily use it to implement any other mode.

Note that, for efficiently implementing the "feedback" modes (i.e. CBC, CFB and/or OFB), which require you to feed the previous encrypted (possibly modified by XORing it with the plaintext) block back into the cipher to encrypt the next block, you have two choices: you can either build the circuitry to do that into your AES module, or you can leave it as the responsibility of the user of your module to do that.

The first option is technically pretty simple (you need to be able to feed the block back through the round function several times anyway) and efficient, but it does make your circuit mode-specific, and requires you to implement some way to select the mode of operation, if you want to support more than one.  For most modes, you also need to handle the encryption and decryption operations differently.

The second option is even simpler (at least from your viewpoint; it might not be simpler for the user of your circuit), but having to feed the output back in through the 8-bit I/O bus could reduce encryption speed considerably (at least by a factor of 2 if the input and output timings are staggered appropriately, by a factor of 3, or more, if they're not).

You don't need to generate a new IV for every input block — indeed, that couldn't possibly work, since the IV is a full input block.  Typically, the IV is supplied as the first block of each multi-block message.  If you do decide to implement the feedback internally, you do generally need to treat this first block somewhat differently from the later ones.  (That's not always the case, though: for example, for CBC and CFB mode decryption, the IV can be treated just like any other ciphertext block, with the user being responsible for throwing the first plaintext output block away.)

There's also a very handy variation on CBC mode encryption where the initial "IV" is simply set to all zeros, and the actual IV is obtained by encrypting the first plaintext block, which should consist of a nonce.  Decryption still works exactly same as usual.  You might want to support this scheme explicitly (avoiding the need to actually feed in the dummy null IV), since it's more resistant to certain attacks involving poor IV generation than standard CBC mode encryption.

In fact, there's a another, more general case where using a fixed (say, all-zeros) IV is OK: whenever each message is encrypted with a different key.  For some applications, this might be a common scenario, in which case you may want to provide it as a general option for any mode.

One final feature you're typically going to need is some way to change the key.  There are applications for which having a single, fixed key permanently embedded in the encryption circuit may be sufficient, and it does simplify the circuit considerably, but for most purposes you do need to support changeable keys (which implies that you need to implement key expansion).

Another simplification you may be able to make, in some applications, is that many modes of operation (such as CTR, CFB and OFB, as well as many AE modes like EAX or SIV) only use the underlying block cipher to encrypt blocks, never to decrypt them.  Although you can generally reuse much of the encryption circuitry for decryption, omitting the decryption parts still makes things a lot simpler.  You do, however, need the decryption circuitry if you want to implement CBC or OCB mode (or, obviously, ECB mode) decryption.


Special equivalent key in symmetric encryption Let $k$ and $k'$ be two keys of symmetric encryption such that for some $m$ we have $ Enc_k(m)=Enc_{k'}(m)$. Is it possible to exist a plain text $m'$ such that $Enc_k(m') \neq Enc_{k'}(m')$.

In fact, is there exist a key which be equivalent only for special plain text?

Yes. Actually it is quite likely that there are quite a few such keys for block ciphers. That said, finding one takes a collision search which may take a lot of time, especially for ciphers with a large block size.

Proving that there are no other messages that permite to the same ciphertext may even be computationally infeasible.

It would not be a good property for a block cipher to have keys that are fully equivalent. It may not directly destroy all trust in the cipher but it would certainly raise a few eyebrows.