Do Weil, Tate, and Ate pairings exist on all elliptic curves? I don't know much about the math behind elliptic curves.
Do Weil, Tate and Ate pairings exist on all elliptic curves? If the answer is negative, then what pairings do MNT, BN and SS curves have?

When we say that an elliptic curve has an embedding degree of $k$, do all these pairings map $E(GF(p))$ to $GF(p^k)$? Furthermore, when we speak of embedding degree, are we assuming a specific pairing?

Which of the Weil, Tate and Ate pairings is more efficient? Are there any security trade-offs between these pairings?

Yes. In fact, you can write the Weil and Ate pairings in terms of the Tate pairing.

Let $E$ be a curve over $\mathbb{F}_p$ of embedding degree $k$ and prime order $r$. The Weil pairing is related to the Tate pairing as
$$
e(P,Q)^\frac{p^k - 1}{r} = \frac{t(P, Q)}{t(Q, P)}\,,
$$
where $t(\cdot,\cdot)$ is the Tate pairing. Likewise, we have
$$
a(Q, P)^{kp^{k-1} } = t(P, Q)^\frac{((t-1)^k - 1)}{r}\,,
$$
where $a$ is the Ate pairing, and $t$ is the trace of Frobenius, i.e., $t = p + 1 - \#E$.

So for all common pairing-friendly curves, all of these pairings exist and are well-defined. The optimal Ate pairing is the most common, since it involves the shortest Miller loop and is often the fastest. But this is not necessarily the case, depending on field sizes, available parallelism, etc.


RSA private key d knowing e,n I need to find RSA private key $(d, N)$ knowing $(e, N)$. It's "own" RSA implementation. As i know
$p$ is random 70 bit number, then $q$ is $p-2^{10} < q < p+2^{10}$
$d$ is max 16 bit long with low number of ones in binary representation.

$e= 4223234360740816682261885795416553301541344119$

$N = 5074772291286459206774040208059072021046562917$

I tried to use Wiener's_attack with implementation from GitHub.

It gives me $d = 1031$. Is it the answer ? How to check if is it valid ?

What are the right ways to find d ?

Yes, in your specific case, $d=1031$ is the answer.

You can check it in the following ways:

Just try it out. Select some arbitrary messages, exponentiate with $e$, apply the modulus and exponentiate them with $d$. If this yields your original message number (like 20 or 5001) you know it's the correct $d$.
Factor $N$ using the exponent. You may want to use one of these algorithms for this. If you can factor this you can be sure to have the correct exponent. Note for the link: $m=e*d$

Now to the other ways there are for your case to find $d$.

Wiener's attack. $d$ is small meaning, Wiener's attack applies. You've used this fact successfully.
Brute-force. The parameters look so weak, that you can even just try out the $2^{16}$ values for $d$.
Factoring $n$. Using the quadratic sieve or a similar algorithm (provided by msieve or even non-dedicated tools) you can factor your 140-bit ($\approx 45$ digits) modulus within a relatively short time (seconds). After having factored $N$ you simply use the factorization to obtain $d$ from $e$.
As the distance between your primes isn't that large ($<2^{10}$) you can as well use Fermat's factoring method, which should yield the parameters $p$ and $q$ reasonaly fast. You proceed as above then.

So you see these parameters are extremely weak, so you shouldn't even think about using them in practice. But as they are so weak I'd guess this is some sort of homework, so it shouldn't be that much of a problem.


PBKDF2 output size vs internal hashing algorithm PBKDF2 allows you to choose an output size as well as the internal hashing function used.

My question is, do these two sizes need to match?

For example, if I'm using PBKDF2 with SHA512, does my output size need to be 512 bits?

I'm a little confused because WebCrypto and CryptoJS allow you to specify SHA512 as the hashing algorithm, but then limit the output key size to the AES max output size, which is 256.

Why is AES even used to generate the final key, and not just a SHA hash of the derived key?

My question is, do these two sizes need to match?

Well, officially no, the output of PBKDF2 is only limited by the following definition from PKCS#5:

dkLen      intended length in octets of the derived
           key, a positive integer, at most
           (2^32 - 1) * hLen

There hLen is the length of the internal hash algorithm.

PBKDF1 is actually limited to hLen - unless you are using the horrible Microsoft implementation which is simply completely insecure and unspecified for anything over hLen of output.

It is however strongly recommended to keep to hLen as output. The reason for this is not that the output is somehow dependent. The problem is that the whole work factor (parameterized by the iteration count) is repeated for each additional block that is required. The problem with this is that attackers do often not need to perform all these additional operations to verify correctness of the input while brute forcing or performing a dictionary attack. So additional output put you at a disadvantage over an attacker.

Try to keep to SHA-512 and a maximum output size of 512 bits or use an additional function such as HKDF to increase the amount of output (or use the KDF multiple times to derive multiple keys/secret values).

  Why is AES even used to generate the final key, and not just a SHA hash of the derived key?

This is a misconception on your part. AES may take the output of PBKDF2 to be an AES key. No AES key operations are however performed within PBKDF2 (AES has a block size of 128 so expecting 256 bytes of output would be strange anyway).

Directly converting the output to a key means that the user doesn't have to "manually" an AES key type from the output of the KDF. This is more secure as the bytes do not have to be copied into the resulting key - and the original bytes don't need to be destroyed (zeroed) either.

In case of hardware crypto the output of the KDF may be kept in the device as well (instead of first copying it to memory of the host device), although this is usually not an issue for PBKDF2 as password handling is usually not performed in specialized hardware.


How to use separate keys for signing and encryption I read that the same key should not be used for both certificate signing and encryption.

I wonder if this is not a problem with PKI/TLS/SSL, the reason being asymmetric encryption is used to transmit the public key (via the certificate).  The public key is used to encrypt a browser generated session key.  The session key is used for symmetric encryption of the actual traffic.

Is that how it works and does that mean it is okay to sign both with the same key?

How would I go about using separate keys?

In TLS 1.2 the Client proposes a list of suites of primitives they are willing to use for TLS. This takes place in clear in the ClientHello message.
You could examine that list and decide one of three things:

The list has a nice modern Forward Secret Diffie-Hellman-style key agreement method you're comfortable using with RSA signatures. You present Certificate #1 for RSA Key #1 and you use the corresponding Private Key to sign stuff in TLS. Certificate #1 says this RSA key is suitable for this purpose (specifically it should set the Key Usage bit 0 digitalSignature).

The list says the client is willing to do RSA key agreement. You present Certificate #2 for RSA key #2 and you use the corresponding Private Key to decrypt the key agreement message from the client. Certificate #2 says this RSA key is suitable for this purpose but not for signing things (probably setting bit 2 of Key Usage aka keyEncipherment -- it should definitely not set bit 0 digitalSignature).

OR 3. You can't accept any of these methods and give up.
Having chosen to behave this way you can now also do TLS 1.3, you should always use Certificate #1 (and the corresponding key) because in TLS 1.3 there is no RSA key agreement mechanism since it is considered dangerous. Because you are using separate keys, a client which is careful about validating Key Usage information can discern that it should not trust Certificate #2 in TLS 1.3 (or doing DH key agreement in TLS 1.2) and so if an attack on your decryption in scenario #2 above is successful those clients are protected and only clients willing to undergo scenario #2 themselves are affected.


Modification of RSA using two inverses, one for P mod (Q-1) and one for Q mode (P-1), instead of inverse d mod [(p-1)(q-1)], more or less secure? Lets say I have the following modified RSA scheme

We choose two large primes P, Q, with additional restriction that these are relatively prime to (p-1) and (q-1)
We choose N = PQ as public key
We calculate $P'$ such that $P'P \bmod (Q-1) = 1$ and $Q'$ such that $Q'Q \bmod (P-1) = 1$
Encryption is $C = M^N \bmod N$
To decrypt, we find M such that
$M = C^{P'} \bmod Q$ and $M = C^{Q'} \bmod P$

which can be shown to be correct using similar proof as RSA.

Is this scheme more secure or less secure than the normal RSA? Better or worse? My gut feeling is that it is less secure because it depends on primes that satisfy condition 1 which reduces the search space. However, more computation is required to check for this in the first place so I can't be sure.

Also this encryption scheme will only result in one public key N compared to (N, e) in the RSA and no private key which seems to suggest less security on the surface

This system was invented in 1973 by Clifford Christopher Cocks of the GCHQ and described in his document (then secret) A note on Non-Secret Encryption, before RSA was published. See this question for more context.

  Is this scheme more secure or less secure than the normal RSA? Better or worse?

On security, we know no difference with RSA. The restriction that $p$ and $q$ are relatively prime to $p-1$ and $q-1$ does not sizably reduce the keyspace, in fact this restriction is always met when $p/2<q<2p$, which is customary in RSA as practiced. And, by using $N$ as the public exponent, nothing more than their product is revealed about the factors. From this standpoint, RSA with small exponent reveals more: with $e=3$, about half the primes are ruled out, and this is not known to make factoring sizably easier. But, like in RSA, factorization is only one of the security threats: we know no reduction to factorization for either scheme.

On practicality, RSA is superior because it can use a small $e$, which greatly speeds-up encryption (and signature verification), with no known drawback if proper padding and leakage protection is used, or $e$ is comfortably above the bit size of $N$. Small $e$ was not in Ronald L. Rivest, Adi Shamir, and Leonard Adleman's A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, in Communications of the ACM, Feb. 1978. But that quickly was added by Rivest's MIT group: it's in the challenge they made for Martin Gardner's A new kind of cipher that would take millions of years to break (in the Mathematical Games column of Scientific American, Aug. 1977).

Cock's paper clearly suggests using the Chinese Remainder Theorem for decryption, which from the standpoint of speed is superior to RSA as initially described. As far as I know, that improvement was not published before Jean-Jacques Quisquater and Chantal Couvreur's Fast decipherement algorithm for RSA public-key cyptosystem, in Electronics Letters, Oct. 1982. It is now standard practice in RSA, because it speeds up things by a factor up to about 4 compared to computing $x^d\bmod N$ by performing all the arithmetic modulo $N$.


What are the integers in an RSA PEM file? I have an RSA Private key file my_private_key.pem with the header -----BEGIN RSA PRIVATE KEY-----. I can parse that with the openssl utility: openssl asn1parse < my_private_key.pem

That shows me a bunch of integers: a 4096 bit integer, a 17 bit integer, another 4096 bit integer, and then five 2048 bit integers.

I understand the textbook RSA primitive where the private key is $(p,q,e)$ where $p,q$ are large secret primes and $e$ is the encryption exponent where $\gcd(e, (p-1)(q-1)) = 1$ and you encrypt plaintext $m$ by $c \equiv m^e \pmod{N}$ where $N=p \cdot q$. How does that textbook version of RSA relate to these integer numbers I see in a .pem file?

I'm sure this is a newbie question. Where do I start to read on this?

Here is a labeled example output (don't worry I created a new key):

Which you can verify for example in Sage. Although, surprisingly, it apparently doesn't allow decryption because the exponent is too large.


How can one break a monoalphbetic substitution chipher at pseudorandom text? Does anybody know how to break monoalphbetic substitution cipher, if it is applied to some pseudorandom text (for example to some surrogate key filed in a database)?

Let us assume that we have only cipher text, and don't know anything about distribution of different characters appearance probabilities, so frequency analysis doesn't work.
Is there some other approach?

Background: I just need to "encrypt" (not really encrypt, possibility to decrypt is not necessary) key fields in a db, keeping the length of it and avoiding collisions (don't ask why).

And I just cannot google out some encryption algorithm which will satisfy both clauses. Cryptographic hash functions are too long, common encryption algorithms can not guaranty absence of collisions, and actually also basically have a limit of length. So the only solution which I can imagine is a substitution cipher, and I want to know how weak it would be in my case.

One problem with a mono-alphabetic substitution cipher is that an attacker would gain a lot of information if (s)he gets just one plain-cipher pair. Given few plain-cipher pairs, the attacker can probably break your full cipher.

You wrote that (at least part of) the encrypted data is a surrogate key. These keys should have all the same format (like 32-bit or 64-bit number) and should be better encrypted with a block-cipher for the required block size (see also the 2nd link in Paŭlo 3rd comment to your question).

If you have also data of different size (which seems to be the case), you should consider taking a family of block ciphers such that you have a (different) block cipher for each byte-length and encrypt the data with the block cipher according to its bytelength.


Encrypting messages for multiple recipients With hybrid cryptography, I want to encrypt a message intended for multiple recipients.

This can be archived (as described here by creating a symmetric secret key, encrypt the message with this key, and then include an encrypted version of the secret key, encrypted with all of the recipients' public keys.

I wonder if it is possible to have a "master recipient" who can decrypt all messages, and then have less privileged recipients who can only decrypt messages encrypted with their specific public key. Will it be possible by some sort of hierarchical keys, to enable a master recipient able to encrypt the secret key even though the secret key is not encrypted the master recipient's own key and added to the message?

Maybe I ought to look into "attribute-based encryption"?

Yes, this is possible. The most natural option is to look at identity-based encryption (I point to the wikipedia page, as it gather some links to various schemes), such as the Boneh-Franklin IBE. An IBE allows to encrypt a message with the identity of the user. After interacting with some trusted authority once in a setup phase, each user can receive the secret key associated to this identity, and decrypt all messages encrypted for their identity. The owner of the master secret key (which is used to derive identity-based secret keys) can decrypt all messages, for any identity. Your intuition about looking into attribute-based encryption is essentially correct, as IBE is a special case of attribute-based encryption.
In fact, you do not need the full power of IBE here, so there is an alternative possibility. The exact feature that you are looking for is enjoyed by the Bresson-Catalano-Pointcheval cryptosystem. Close variants of this scheme were invented simultaneously the same year, by Damgа̊rd and Jurik, and by Cramer and Shoup. It allows to perform the following operation:

Generate a pair (master public key, master secret key) $= (\mathsf{mpk},\mathsf{msk})$
Given the master public key $\mathsf{mpk}$, any user $P_i$ can generate a pair public key / secret key $(\mathsf{pk}_i,\mathsf{sk}_i)$
A message encrypted with $\mathsf{pk}_i$ can be decrypted either with the corresponding secret key $\mathsf{sk}_i$, or with the master secret key $\mathsf{msk}$.

Note that unlike IBE, you cannot simply encrypt using the identity of a user in this system. However, generating a pair $(\mathsf{pk}_i,\mathsf{sk}_i)$ can be done by any user, using only the master public key (while in IBE, the mastersecret key is needed to derive the secret key associated to an identity), so you do not need to have a trusted authority at this step. This might make this scheme more suited than IBE for your exact application.
If you are familiar with the Paillier cryptosystem and the ElGamal cryptosystem (otherwise, ignore what follows), the idea of the scheme is quite natural: a ciphertext is of the form $(g^r \bmod n^2,(1+n)^mh^r \bmod n^2)$, where $n$ is a product of two safe prime, and $(g,h)$ is some specific public key. Given the factorization of $n$, one can decrypt this ciphertext exactly as a Paillier ciphertext, by ignoring the first part of the ciphertext (the second part is exactly a Paillier ciphertext). Alternatively, given $s$ such that $h = g^s$, the ciphertext can be decrypted with a standard ElGamal decryption.


Counting the number of binary solutions of quadratic system I have a quadratic system of equations related to a balanced RSA modulus $n=pq$ (i.e. $\log p\approx\log q$), and I want to give an upper bound on the number of solutions. Indeed, let $p_i,q_i$ be binary variables, and let $c_i$ be integers such that $0\leq c_i\leq i+1$.

$$\left\{\begin{array}{ll}
p_0q_0&=c_0\\
p_0q_1+p_1q_0 &= c_1\\
p_0q_2+p_1q_1+p_2q_0 &= c_2\\
p_0q_3+p_1q_2+p_2q_1+p_3q_0 &= c_3\\
&\vdots \\
\sum_{i+j=k}p_iq_j &= c_k
\end{array}\right.$$

Given the fact that one solution to this system exists (i.e., the complete factorization $p,q$), I wanted to quantify the number of other solutions to this quadratic system.

I know that there are lattice representations that help in this direction, and probabilistic and deterministic algorithms that actually solve them. But I want just to have an estimate on the number of solutions, maybe taking into account the symmetry of the system. A hint or reference will be highly appreciated.

Actually, it would appear that a standard breadth-first search works for this specific problem.

The algorithm tracks all the solutions that satisfy the equation up to bit $n$, and for each such solution, it considers all possible extensions to bit $n+1$ (there are four), and whether they satisfy the condition on $c_{n+1}$.

If you use this algorithm on the standard factorization problem, it fails miserably (as the number of intermediate solutions approximately doubles at each step until you hit the half-way point); this happens because each extension satisfies the next condition with probability 0.5.  However, for this problem, the condition that needs to be satisfied is $\sum_{i+j=k}p_iq_j = c_k$, which for large $k$ has a considerably smaller probability of holding for an incorrect solution, and hence incorrect solutions are pruned much faster.

I threw together an implementation, and it showed promise; given the arbitrarily product $314159 \times 271829$, such a state search gave a maximum of 22 intermediate solutions (11, really, as I counted solutions with swapped $p$ and $q$ separately), and this was after processing bit 11.

This finds all the solutions fast enough that you should be able to use this to obtain a count.


Efficiency of computing $e(P,Q)$ Vs $g^a \pmod{p}$? The definition of $e$ can be seen here. I want to know the accurate comparison of efficiency between $e(\cdot,\cdot)$ and $g^a \pmod{p}$. If  computing $e(P,Q)$ is less efficient than computing $g^a \pmod{p}$, should we prefer $g^a \pmod{p}$ to $e(P,Q)$ when designing protocols?

Also, what is the reason for defining the pairings on an elliptic curve? Is it to solve the multiplication of points over the elliptic curve?

p.s. Sorry to have a lot of questions, I'm new to elliptic curve cryptography..

Firstly, there is not one definition of a pairing.

A pairing is a bilinear function: you have three finite groups $G_1$, $G_2$ and $G_3$; a pairing is a function $e$ such that, for all $(g_1,g_2) \in G_1\times G_2$ and all integers $a$ and $b$, then $e(g_1^a,g_2^b) =e(g_1,g_2)^{ab}$ (I am here using multiplicative notation for the three groups). Why would you want such a function, in a cryptographic setting ? Basically, if you can have the following properties together:

$G_1$, $G_2$ and $G_3$ have known, finite orders.
Computations on these groups is easy.
The computational Diffie-Hellman assumption holds on the groups.
A pairing function $e$ can be defined and easily computed on these groups.

Then we can use the groups and the pairing function to power some interesting cryptographic protocols, in particular Identity-Based Encryption, which would be hard to obtain without pairing-friendly groups. To state things in a very general way, "normal" groups are for protocols which involve interactions between two parties (e.g. Diffie-Hellman) while pairing-friendly groups are for protocols which involve interactions between three parties.

So the cryptographic question is: do we know pairing-friendly groups ?

Right now, the only practical candidates we have for pairing-friendly groups are some special elliptic curves, which allow for a few distinct pairing functions (Weil, Tate, Ate and Eta pairings, the last two being subvariants of the Tate pairings). So we don't use pairings to "solve things" on elliptic curves; we use elliptic curves so that we can have computable pairings, which open the possibility of nifty advanced protocols.

(Note that initially, Weil and Tate pairings were first investigated as mechanisms to break elliptic curves. Fortunately, usual elliptic curves don't allow for computable pairings -- if you try to apply Weil or Tate pairing on a "normal" curve, you will find that it entails computations on integers which would not fit in the RAM of any computer, even if the computer was as big as the Moon. Pairing-friendly curves are in fact "slightly weakened curves" specially crafted so that pairings are computable, but not to the point that they allow a fast break of the said curves.)

Then there are details. For instance, in some protocols we want a symmetric pairing where $G_1$ and $G_2$ are the same group; while in other protocols we want the opposite: $G_1$ and $G_2$ shall be distinct groups, with, for instance, a one-way morphism from $G_2$ to $G_1$ (but not in the other direction). You will not use the same curves and the same kind of pairing for all cases.

So your question cannot have any simple answer except that "it depends". We can still give orders of magnitude: for a given security level (e.g. that of 2048-bit RSA), usual pairings will entail a computational cost which is about 8 to 12 times the cost of decryption with 2048-bit RSA. Don't try to read too much in that figure, though. What must be remembered is that, for instance, the BLS signature scheme allows for short signatures (shorter than DSA or ECDSA) but implies a computational overhead (for signature verification) which is not necessarily negligible.


Is there any benefit to *really* strong passwords? Suppose you had these two passwords:

password_one = "Z;$]bnNvY3I-Ww]R4qm7PpiE/@y9Qz$cNk{d3"
password_two = "4tjDqq])G-^u:PT~X]QBTa,XqUk[o9`(p?iC`w8*)*T9t\@l+^+U04m@_8CXV:E7L\R]\>N6M.0E|%Ud_f*]bN*rn^;FX7\M%5t?"

It seems to me that they are both strong. Is password_two harder to crack than password_one?

I guess this depends on what sort of hashing is involved. What if Bcrypt or sha512 are used, would there be any benefit for using password_two?

I'll assume those were generated by selecting characters independently and uniformly at random, out of a set of 95 characters.  Entropy is the base 2 logarithm of the number of equiprobable choices, so each character chosen independently at random contributes $\log_2(95) \approx 6.6$ bits of strength to your password.  So the strength of password_one is about $37 \times 6.6 = 244.2$ bits.

That's already stronger than any cryptographic key will ever realistically need to be—it's comparably strong to a 256-bit key.  It's strong well past the point where the choice of password hashing algorithm is relevant; if people could be reliably counted on to memorize passwords this strong, we wouldn't need such algorithms.  People choose terrible passwords; the often-cited XKCD password strength comic famously pegged passwords like Tr0ub4dor&3 at about 28 bits, and even that is likely much better than average.

That means that your password_one is, arguably, total overkill, because:

Passwords need to be user-friendly.  For example, they need to be convenient to type or input into one's device.
If your password is this crazy strong, that just means that your weak point is somewhere else, and it's likely way, way weaker than the crazy password.  You're well past the point of diminishing returns.

If you're just a regular Jane or Joe who is not subject of special interest by spy agencies and such, I think 80-bit(ish) strength passwords are plenty strong enough for website logins; a 12 character random ASCII character password (e.g., Z;$]bnNvY3I-) is at about this level, and much more convenient than what you're doing.  For password-based encryption you could consider going up to about 128-bit strength.


Security of the AES with a Secret S-box In this paper they change the $AES$ S-box to a uniformly random one and answer the questions:

How does the security of AES change when the S-box is changed by a secret S-box?
Would it be safe to reduce the number of rounds?

I have tried reading the paper but there are some things I do not understand.

Are the S-boxes they are considering just random permutations of bytes that fit into an $8 \times 8$ table? How might they have chosen all the entries to get the S-box?
Are they choosing a random S-box and then leaving it unchanged thereafter?
In Section $3.1$ they state differential cryptanalysis will not pose a threat to variants of $AES$ where the S-box is replaced by a randomly chosen $8$-bit box. This is confusing. Do they mean one $8$-bit element in the S-box? I thought the S-box was $256$-bit, not $8$.
Still referring to Section $3.1$. If a random S-box is secure against DCA and LCA, why make such an effort to design the one currently in use?
How does a random S-box cause the secret information to go from $128$ to $256$ bits (depending on the key size) to $1812$ to $1940$. I understand there is now more secret information owing to the secret S-box but I cannot see where these numbers ($1812$ to $1940$) come from.

Are the S-boxes they are considering just random permutations of bytes that fit into an 8×8 table? How might they have chosen all the entries to get the S-box?

Yes, they chose a random s-box.

  Are they choosing a random S-box and then leaving it unchanged thereafter

Yes, it was unchanged.

  In Section 3.1 they state differential cryptanalysis will not pose a threat to variants of AES where the S-box is replaced by a randomly chosen 8-bit box. This is confusing. Do they mean one 8-bit element in the S-box? I thought the S-box was 256-bit, not 8.

AES s-box size is 8-bit (8-bits in X 8-bits out), which is 256 entries, represented as a 16x16 table of bytes, which is 4+4 input bits with 8 output bits.

  Still referring to Section 3.1. If a random S-box is secure against DCA and LCA, why make such an effort to design the one currently in use?

A random s-box must be represented as a table in both machine code as well as in analysis of the cipher, the one chosen for Rijndael can be represented as an equation or a much smaller block of code. It also has better differential and linear properties than a random s-box, even if random was sufficient.

  How does a random S-box cause the secret information to go from 128 to 256 bits (depending on the key size) to 1812 to 1940. I understand there is now more secret information owing to the secret S-box but I cannot see where these numbers (1812 to 1940) come from.

I am guessing the extra bits was the information required to generate the s-box, apparently 1684 bits.

Despite that fact, and the fact an attacker does not know the s-box, they were sill able to create practical attacks up to 6 rounds, there are other properties of s-boxes, and random ones usually suck in regards to those properties, where they do well is in algebraic complexity.


Creating Random Pad from XORed Sections of Pi If two strings of equal length from random offsets in Pi were XORed together, would this result in a cryptographically secure random number suitable for use in a one-time pad? If so, would this mean that using a secure low-bandwidth channel, you could bass three digits (two offsets and a length) to provide an arbitrarily long pad?

There's no benefit whatsoever to using XOR here. Pi is already believed to be Normal which means the stream of digits is indistinguishable from random in every base.

The offset into Pi functions as a key, for your system to be secure this key must be very large (e.g. several dozen decimal digits long) and chosen entirely at random, and it must not become known to anybody except the communication parties. With those constraints you should just use a stream cipher which is intended for this purpose.

If you just believe that "Nobody" would guess that your "three digits" are the key to a cipher based on Pi and so it's safe to just transmit the key to the other party you're relying on Security by Obscurity and might just as well use mirror writing or pig latin or something.


Confused about terminology in the many flavors of security I am learning about cryptography from diverse sources, and I have found terminology a bit confusing.

In principle, I understand the difference between the symbolic model and the computational model. However, then I am confused when I see things like :

information-theoretic security,
computational security,
concrete security,
asymptotic security,
perfect security.

What is the relation of all these with the symbolic and computational models? What are the relationships between them?

Is there a source where I can make sense of the terminology in a unified fashion?

To explain, I'll exercise these models on an example, namely that of LoR-CPA-security.

The LoR-CPA game $\operatorname{Priv}^{\text{cpa}}_{\mathcal A,\Pi}(n)$ for a cipher $\Pi=(\operatorname{Gen},\operatorname{Enc},\operatorname{Dec})$ and a security parameter $n$ against a probabilistic Oracle-Turing-Machine adversary $\mathcal A$ goes as follows:

$k\gets \operatorname{Gen}(1^n)$
Uniformly at random generate a bit $b\stackrel\$\gets\{0,1\}$
Define $\mathcal E(m_0,m_1)=\operatorname{Enc}_k(m_b)$
Run the adversary with encryption oracle access to $\mathcal E$: $b'\gets \mathcal A^{\mathcal E(\cdot,\cdot)}(1^n)$
Output 1 if $b=b'$ and else output $b$

Then we define the advantage $\mathbf{Adv}^{\text{cpa}}_{\mathcal A,\Pi}(n,q,t,s)=2\cdot \Pr[\operatorname{Priv}^{\text{cpa}}_{\mathcal A,\Pi}(n)]-1$ where $\mathcal A$ must run in $t$ steps, only use $s$ cells of space and make at most $q$ queries to its oracle.

Now for the definitions:

Symbolic model: From what I gather from the linked paper (PDF) this would take the above definition and remove all occurences of the security parameter and runtime / space restrictions from all algorithms, which should be equivalent to the notion that the only thing you know / can learn is the correctness property.
Perfect Security / Information-theoretic security: They are the same and ask for a scheme that for all $n$: $\mathbf{Adv}^{\text{cpa}}_{\mathcal A,\Pi}(n,\infty,\infty,\infty)=0$ holds. This is not always achievable.
Asymptotic Security: This one asks that there exists a negligible function $\varepsilon$ such that $\mathbf{Adv}^{\text{cpa}}_{\mathcal A,\Pi}(n,\operatorname{poly}(n),\operatorname{poly}(n),\operatorname{poly}(n))\leq \varepsilon(n)$ for all $n$ larger than some $n_0$ and some polynomial $\operatorname{poly}$.
Concrete Security: This one demands a concrete relation / statement for the security of the scheme, i.e. there must exist some function $f$ such that $\mathbf{Adv}^{\text{cpa}}_{\mathcal A,\Pi}(n,q,t,s)\leq f(n,q,t,s)$ and it is up to the user to judge whether $f$ is small enough for a given parameter set to be considered secure for their application. This is the preferred notion for non-complexity-theoretical results.

The computational model is then an umbrella term for the last three bullet points from above.
Computational security is usually an umbrella term for the last two bullet points from above.
Even though I used CPA-security as the example, the above applies to all security notions that define an advantage, except for the algebraic inference in the symbolic model.


How do I convert the definition of E-521 into a curve definition a la Bouncy Castle? I am currently trying to create an ECCCurve for E-521. Unfortunately, it is not currently a named curve in the library I am using, so I will have to define it manually.

I am using the definition of the E-521 curve provided here:

E521 is a curve over GF(2^521-1), formula x^2+y^2=1-376014x^2y^2,
basepoint
(1571054894184995387535939749894317568645297350402905821437625
18115230499438118852963259119606760410077267392791511426719338990
5003276673749012051148356041324, 12), order 2^519 -
3375547632585017057891076304187826360719049612140512266186351500
85779108655765, cofactor 4.

The two curve definitions I can choose from are FpCurve and F2mCurve. I'm not sure which one to choose for this. I have looked here. Unfortunately, I don't know how to extrapolate which one to use based just on the knowledge that E-521 is an Edwards curve.

Is an Edwards curve not compatible with the base classes that are defined in the library? Do I need to wait for further development there, or can I risk attempting to implement it myself? The latter is obviously a question I will likely have to answer myself, but some extra information on the risks/other implementations I could examine would be helpful.

Bouncy Castle does not support curves of the Edwards form (such as the one E-521 has). See related question: Elliptic Curves of different forms
Bouncy Castle's FpCurve supports curves of the Weierstrass simple form. You can convert Edwards curves to this form by a series of (complex) calculations. SafeCurves shows you the necessary equations. First convert the Edwards curve to Montgomery form, then to Weierstrass form.
Unfortunately doing this will result in absolutely huge numbers, which - on top of the fact that Edwards curves are computed faster than Weierstrass curves - results in poor performance.

Appendix: Curve forms

Weierstrass: $y^2 = x^3 + ax + b$
Montgomery: $By^2 = x^3 + Ax^2 + x$
Edwards: $x^2 + y^2 = 1 + dx^2y^2$


Is TLS finished message encryption at record protocol redundant? TLS finished message is encrypted under the record protocol's current cipher state. Being able to authenticate FINISHED message at record protocol proves that the genuineness of peer endpoint. Verifying handshake_hash proves that the handshake has not been tampered by MITM.

The verify_data in FINISHED is calculated using PRF and master secret. So the verification of verify_data should be a sufficient proof of both the authentication of peer and handshake message sanity.

Why additionally the record protocol does cipher operation on FINISHED message?
I think it could have been equivalent if FINISHED message were sent before change_cipher_spec.

If you do Finished after change_cipher_spec, and since Finished has to be the first message after setting the cipher spec, you get the added benefit of requiring a successful decryption of a message before any (potentially sensitive) user data is transmitted. This step serves as an extra "checksum".

From Section 7.4.9 of RFC 5246: (emphasis mine)

  The Finished message is the first one protected with the just
        negotiated algorithms, keys, and secrets.  Recipients of Finished
        messages MUST verify that the contents are correct.  Once a side
        has sent its Finished message and received and validated the
        Finished message from its peer, it may begin to send and receive
        application data over the connection.

Edit:

You wonder if encrypting Finished is unnecessary given that verify_data provides sufficient authentication against tampering. I claim that an sending an unencrypted Finished message would be quite disastrous for TLS.

The end of a normal TLS handshake looks as follows:

$\text{client} \rightarrow \text{server}:$ change_cipher_spec

$\text{client} \rightarrow \text{server}:$ Finished $a_k$

$\text{server} \rightarrow \text{client}:$ change_cipher_spec

$\text{server} \rightarrow \text{client}:$ Finished $a_k$

$\text{client} \rightarrow \text{server}:$ encrypted application data transmits... $m_k$

Here, $a_k$ and $m_k$ are the authenticaton code for Finished and session data keyed by $k$. It's important to reiterate that before a change_cipher_spec message is received, the current cipher suite offers no encryption or authentication; it's still pending the negotiated parameters upon receipt of change_cipher_spec.

Now imagine Andy Adversary on the network observing this handshake. In the special case where the negotiated cipher suite only handles authentication and not encryption, Andy removes the change_cipher_spec messages, so that the client and server never update their cipher suites and thus never enable authentication or encryption with the negotiated parameters. Welcome to catastrophe. Now Andy sits in the middle, stripping off authentication fields from Finished messages and later sensitive session data. So now you have no authentication either.

Here's the modified, defeated handshake:

$\text{client} \rightarrow \text{adversary}:$ change_cipher_spec

$\text{client} \rightarrow \text{adversary}:$ Finished $a_k$

$\text{adversary} \rightarrow \text{client}:$ Finished $a$

$\text{server} \rightarrow \text{adversary}:$ change_cipher_spec

$\text{server} \rightarrow \text{adversary}:$ Finished $a_k$

$\text{adversary} \rightarrow \text{client}:$ Finished $a$

$\text{client} \rightarrow \text{adversary}:$ unencrypted application data transmits... $m_k$

$\text{adversary} \rightarrow \text{server}:$ unencrypted application data transmits... $m$

It's easy for Andy Adversary to strip off the MAC field since there's no encryption. So now he has not only access to unencrypted, unauthenticated messages, but he can also forge whatever messages he likes.

If encryption were part of the cipher suite as is normal, the attack is much harder, but the point is that by passing in Finished after change_cipher_spec, you eliminate even the possibility of the attack.

What I have described here comes directly from Wagner and Schneier, who knew of this attack by 1997. As a matter of fact, they note that Netscape's SSL 3 implementation was vulnerable to it. Read Section 4.3 of that paper for more details.

Their recommendation to prevent such attacks?

  The simplest fix is to require that a SSL implementation
  receive a change cipher spec message before
  accepting a finished message.

They recognize this as a basic flaw in the specification of SSL, which of course was corrected in TLS:

  Some readers might complain
  that this requirement ought to be obvious with a moment’s
  reflection, even if it is not explicitly stated in
  the SSL specification. We cannot fault such clarity of vision.

In general, this is not the only attack that can be prevented by the "checksum" argument, or what Bellare and Rogaway call matching conversations, where both client and server verify encryption and authentication before transmitting sensitive data. See Section II-1 for another.

Conclusion: sending an encrypted Finished after change_cipher_spec is the simplest solution to protect the change_cipher_spec message.


How to show that a one-way function proves that P ≠ NP? According to this, the existence of a one-way function proves P ≠ NP. What is the proof of this?

One way to show this is that if P = NP, then any function is easy to invert. P and NP are about decision problems though, not computation problems.

(Basically, my question is about how statements about decision problems relate to computational problems.)

It is easier to prove that $P = \mathit{NP}$ implies one-way functions do not exist:

Let $P = \mathit{NP}$, and assume $f$ is one-way. Then consider the language $L$ of pairs $(x^\ast, y)$ such that $x^\ast$ is a prefix of some $x$ satisfying $f(x) = y$. $L$ is in $\mathit{NP}$ because $x$ itself is a witness  (up to minor formal details; see this question too) we can use to verify the pair in only polynomial time—recall that a one-way function can be computed in poly-time.

But we have $P = \mathit{NP}$, and we can use a decider $D$ for $L$ to "invert" $y$. Receiving the input $(y, 1^n)$ ($n$ being the safety parameter), start with the pair $(\varepsilon, y)$, i.e. with the empty word as a prefix, and use $D$ to incrementally add bits to the prefix part until you obtain $(x,y)$ with $f(x) = y$. Such an algorithm runs in poly time because it is guaranteed there exists an inverse image to $y$ of length at most $n$. It follows that $f$ is not one-way, and we have a contradiction.

Regarding your question about the relation between decision problems and computational ones: the whole point of the $P = \mathit{NP}$ dilemma is answering whether computing a solution is as hard as simply verifying it or not. This is because non-determinism virtually allows us to "cheat" and circumvent wasting any time in computing the answer; we only need to guess it and check whether our guess was correct or not.

An interesting consequence of the statement above is that the assumption of one-way functions is actually stronger than $P \neq \mathit{NP}$. This is in line with the famous hierarchy of cryptographical assumptions known as Impagliazzo's five worlds.


Using hashes as passwords I have thought of a system for generating passwords which works as follows:

Take the following items:

A password, such as williamwallace.
A secret 1000 digit number which is stored on my computer.
The name of a website.

Create a password like this:

hex(sha512(site + password + number))

For example:

hex(sha512('google' + 'williamwallace' + '1456 … 3889'))

The generated hash can then be used as your password. How secure is this system?

I don't see any obvious security problems in your approach. You can look into key derivation functions, that can provide some additional security in case one of the following occurs:

Your password leaks
Your secret number leaks
A weakness is identified in the hash function

There is a few usability issues, that would have to be addressed as well:

Different sites have different password policies (minimum password length, maximum password length, required characters, forbidden characters). There is no single function mapping from binary hash value to password string, which can be used with every password policy. Your current approach of using a hexadecimal string will run into two issues: Maximum length of password being 8 or 20 characters is not unusual. Requiring at least one non-alphanumerical character is also not unusual. Solution I propose for this is that you have different functions mapping from binary hash to password string, such you can choose one suitable for each site's particular policy. I think base64 is a better default than hexadecimal.
You may sometimes need to change the password on individual sites more frequently than others. Along with the site name you could include information about when the password was generated. A granularity of one month seems like a good balance between these two factors:

How often you may need to be able to change the password.
How easy you can remember the correct time as well as the possibility to brute force this single field, in case you forgot when the password was created, but remember everything else.

You may need to change your master password and keyfile because one of the two has leaked. But changing passwords for every site right away may not be feasible. To address this purpose, I would do the following:

Create a new secret number and associated password
Create a file containing the old password and secret number both encrypted using the new secret number and password.
Before starting to use the new password check a couple of times a day for a couple of days, that you can remember the new password. Verify this by decrypting the encrypted data and compare the secret number.
Once you have proven enough times that you can remember the new password, destroy the old clear text secret such that old passwords can only be accessed by decrypting using the new password.
From this point use the new data for all new passwords and only use the decryption for passwords, that have not been updated yet.
Record when the date on which the switch over was made.


Insecure third party connection My organization processes some PII data and shares it with an outbound connection (outflow only) that is a third party. The data transfer transactions occur without human intervention. That outbound connection is encrypted using TLS 1.0 with RC4-MD5 weak hash algorithm. By industry standards TLS 1.0 is insecure. Although other controls exist such as a firewall, are there are risks pertaining to this connection with the current encryption? Please help explain what are the potential attacks that can occur. Can lease lines with socket protocols instead of web protocol be encrypted?

There are two facets in the use of TLS-1.0 with TLS_RSA_WITH_RC4_128_MD5. From a cryptographic point of view:

TLS-1.0, as a protocol, is not broken. It does a number of things in a suboptimal way, forcing implementations to jump through intricate and topologically improbable hoops in order to avoid side-channel leakages. Recent implementations ought to be fine, but of course anything which is deployed is fast becoming non-recent unless it is promptly updated whenever a security fix is published by the vendor.
RC4 has a number of weaknesses, mostly biases which are serious enough to be exploited in practice, if the usage conditions are right (for the attacker). Worst bias is on the second byte of an RC4-generated stream: that byte will have value 0x00 with probability about 1/128 instead of the expected 1/256. Thus, if you send the same secret data at the start of the stream for a few thousands of distinct streams, then the attacker will be able to guess the second byte of that secret data.

If your TLS usage really is HTTPS, then the first few dozens or hundreds of bytes of the stream will be an HTTP header, most of which being non-secret, and the data you want to protect will be subject to less serious encryption biases -- the attacker will need to observe connections by the millions, not the thousands. From an academic point of view, this is still utterly broken; but in practice, this will still be quite hard to leverage for attackers.
MD5 is broken with regards to collisions. In TLS-1.0, MD5 is used as part of HMAC, and right now nobody knows how to attack HMAC/MD5.

From a security point of view, your use of TLS-1.0 with RC4+MD5 is thus probably not a real issue in itself. However, it is a symptom. If you still use such a protocol version and algorithms, then chances are very high that your implementation is an old library which has not been updated in the last decade, thus probably riddled with numerous known vulnerabilities that would allow attackers to simply buffer-overflow it to death. Real-world attackers don't resort to breaking cryptography upfront unless they have no other choice.

Therefore, while using TLS-1.0 with RC4+MD5 is not an immediate danger, it indicates that there are very serious structural issues in your software management procedures, namely that they don't exist. This is what you should strive to fix.

Also, if you handle PII, then chances are that you must comply to some regulations. If conformance auditors see you using TLS-1.0, RC4 or MD5, then they will skin you alive.


Is a using salt important when creating a hash data validator? I am creating a service that will return an set of objects, which will be used by multiple systems.  At the end of the process, one (or more) of the objects will be sent back to our system for association.

My service basically checks our system and gets valid solutions.  I want to create a hash to validate that the object returned to us has not had certain values altered from the solution object we gave out, and to make certain that the solution being presented originated from our original service.

The source value that will be hashed will already be at least 80 bytes long.  Is there any real value in adding a salt to that value prior to hashing?

The answer to that depends on the details of your system, and specifically whether someone other than you can modify the hash.

If you store the hash in your database, and retrieve the expected hash value from your own database to compare it with the actual hash (when checking to make sure that those certain values have not been altered), there's no point in using the salt.  The only thing someone could try to do to fool you is to find a modification to the object in such a way that leaves the hash result the same; if you use a collision-resistant hash function, he won't be able to do that.

On the other hand, if you return the hash along with the set of objects, and at the end of processing, the hash will be sent back to your system along with the objects, well, one thing someone might do is modify the objects, and then modify the hash to reflect that change; because the hash function can be evaluated publicly, they can do that.

In this second case, introducing an unknown salt value certainly is one way to attempt to prevent this attack, but it's probably not the best.  What you really need in this case is a Messsage Authentication Code (MAC) instead of a hash; I would recommend using HMAC based on the hash function you're already using; it's only a constant amount slower than the hash function, and was designed specifically to be strong in this attack model.


Bijective encryption function in Paillier cryptoststem In Paillier cryptoststem many ciphertexts can correspond to the same plaintext. How can I modify the scheme so to make the correspondence between ciphertexts and plaintexts a one to one correspondece? I've already eliminated the randomness from the scheme (i.e. all encryptions are done with the same $r$).

My reason for this is that I want to compute the arithmetic mean of two encrypted numbers by repeatedly subtracting 2 (which I can do no-problem) until I hit 0 which I then need to detect.

How can I modify the scheme so to make the correspondence between ciphertexts and plaintexts a one to one correspondece?

You do realize that this would make encryption insecure, don't you?  After all, someone who knows what an encrypted 1 looks like can subtract 1 until he gets one; this immediately reveals what value the original ciphertext stood for.

If security is not a requirement, might I suggest using the identity function as your encryption mechanism.  It is deterministic, it can be implemented quite efficiently, and for that matter, it is fully homomorphic.


ECC public key encryption without symmetric cipher Imagine the following scenario. A process is running in background and permanently encrypting some data. An adversary has full control of the process, e.g. it can dump the process memory any time and read the symmetric key. It is essential that the adversary cannot decrypt the data, therefore only public-key encryption without any symmetric cipher component is feasible.

What would be the best method for data encryption in this scenario using ECC?

ECC cant really be used to encrypt and decrypt data - it doesn't have the required properties. An asymmetric cipher such as RSA would have to be used, as this can encrypt and decrypt data.

ECC can be used for bilateral key exchanges, and to sign/verify data. RSA can sign/verify data, do KEMs, and encrypt/decrypt data.


Show that the equal difference property exits for a modified DES encryption system My cryptology professor gave us this problem on a past homework assignment and I only managed to get one of the 3 parts correct. Needless to say, I want to know how to do the other two parts as well. The question is as follows:

  Consider the following DES-like encryption system that operates on 16-bit strings.
  The system takes the input and divides it into two 8-bit string $L_0$ and $R_0$.
  One round of encryption starts with $L_{i-1}$ and $R_{i-1}$
  and the output is $L_i=R_{i-1}$ and $R_i=L_{i-1}\oplus S(R_{i-1})\oplus K$,
  where $K$ is the key.

  The function S rotates the bits of $R_{i-1}$ to the right.
  More precisely, if $R_{i-1}=b_0\|b_1\|b_2\|b_3\|b_4\|b_5\|b_6\|b_7$
  then $S(R_{i-1})=b_7\|b_0\|b_1\|b_2\|b_3\|b_4\|b_5\|b_6$.

The two parts that I was not able to get are:

  1) Explain briefly why if $A$ and $B$ are bit strings, then $S(A\oplus B)=S(A)\oplus S(B)$

  2) If $M$ is the plaintext, let $E_K(M)$ denote the process of encrypting $M$ using one round of the above process. Show that $E_K$ has the equal difference property, namely that if $A\oplus B = C\oplus D$, then $E_K(A)\oplus E_K(B)=E_K(C)\oplus E_K(D)$.

Anyway, if someone could provide a complete explanation (answer included) on how to the 2 above questions, I would greatly appreciate it! Thanks in advance!

For 1) you need to show that $S(X)$ is linear with respect to xor.

We can define $S(X)$ as:

$S(X) = (x_{7}, x_{0}, x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6})$

And define $A \oplus B$ as:

$A \oplus B = (a_0 \oplus b_0, a_1 \oplus b_1,a_2 \oplus b_2,a_3 \oplus b_3,a_4 \oplus b_4,a_5 \oplus b_5,a_6 \oplus b_6,a_7 \oplus b_7,)$

So we have:

$S(A \oplus B) = (a_7 \oplus b_7,a_0 \oplus b_0,a_1 \oplus b_1,a_2 \oplus b_2,a_3 \oplus b_3,a_4 \oplus b_4,a_5 \oplus b_5,a_6 \oplus b_6)$

$=(a_{7}, a_{0}, a_{1}, a_{2}, a_{3} a_{4}, a_{5}, a_{6}) \oplus (b_{7}, b_{0}, b_{1}, b_{2}, b_{3} b_{4}, b_{5}, b_{6})$

Which by definition is:

$=S(A) \oplus S(B)$

For number 2) we'll first show that if there is some difference $D = A \oplus B$ then $E_k(D) = E_k(A) \oplus E_k(B)$.

We can define $E_K(M)$ as:

$M_R || (M_L \oplus S(M_R))$

So given:

$E_k(A) \oplus E_k(B)$

$=\big[A_R || (A_L \oplus S(A_R))\big] \oplus \big[B_R||(B_L \oplus S(B_R))\big]$

$=(A_R \oplus B_R)||(A_L \oplus S(A_R) \oplus B_L \oplus S(B_R))$

And using the property proved in 1) you get:

$=(A_R \oplus B_R)||(A_L \oplus B_L \oplus S(A_R \oplus B_R))$

And because $D = A \oplus B$:

$=(D_R||(D_L \oplus S(D_R))$

$=E_k(D)$

Now we can show the equal difference property holds:

$A \oplus B = C \oplus D$

$E_k(A \oplus B) = E_k(C \oplus D)$

$E_k(A) \oplus E_k(B) = E_k(C) \oplus E_k(D)$


What is the difference between the 23 bi-affine and the 39 fully quadratic equations of the rijndael sbox? In Cryptanalysis of Block Ciphers with Overdefined Systems of Equations Nicolas Courtois and Josef Pieprzyk define 23 so called bi-affine equations (in Appendix A of the paper) between the input x and the output z of the rijndael sbox.

Then they say in A.1 that it is possible to get "not only" 23 bi-affine but 39 fully quadratic equations.
And they further describe that the additional 16 equations come from a) $x^4y = x^3$ and b) $y^4x = y^3$.
($y = x^{-1}$ is the result of the inversion in the sbox)

I assume they produce these 16 equations in the very same way how they generated the 23 bi-affine equations (which is described here providing more details):

They transform/rearrange the equations a) and b) to have 0 on one side.
Then they "split" each equation a) and b) in 8 equations for each coefficient, so we have 16 equations in total for both a) and b).
Then they substitute all the $y_i$ using the affine transformation of the sbox:
$$
z = M\cdot y + \textrm{63}_{16} \\
y = M^{-1}\cdot z + M^{-1} \cdot \textrm{63}_{16} \\
  = M^{-1}\cdot z + \textrm{05}_{16} \\
$$
which resolves to:
$$\begin{cases}
y_7 = z_{1} + z_{4} + z_{6} \\
y_6 = z_{0} + z_{3} + z_{5} \\
y_5 = z_{2} + z_{4} + z_{7} \\
y_4 = z_{1} + z_{3} + z_{6} \\
y_3 = z_{0} + z_{2} + z_{5} \\
y_2 = z_{1} + z_{4} + z_{7} + 1 \\
y_1 = z_{0} + z_{3} + z_{6} \\
y_0 = z_{2} + z_{5} + z_{7} + 1 \\
\end{cases}
$$

I hope these steps are correct, but this way I get to the same 23 bi-affine equations as listed in the papers 1 and 2.

If I do this with a) and b) I get the following result (only one equation out of 16 as example):
$$
0 = x_{1}^{4} z_{0} + x_{6}^{4} z_{0} + x_{0}^{4} z_{1} + x_{1}^{4} z_{1} + x_{2}^{4} z_{1} + x_{7}^{4} z_{1} + x_{1}^{4} z_{2} + x_{2}^{4} z_{2} + x_{4}^{4} z_{2} + x_{6}^{4} z_{2} + x_{6}^{4} z_{3} + x_{7}^{4} z_{3} + x_{0}^{4} z_{4} + x_{1}^{4} z_{4} + x_{3}^{4} z_{4} + x_{4}^{4} z_{4} + x_{5}^{4} z_{4} + x_{7}^{4} z_{4} + x_{1}^{4} z_{5} + x_{3}^{4} z_{5} + x_{4}^{4} z_{5} + x_{5}^{4} z_{5} + x_{0}^{4} z_{6} + x_{1}^{4} z_{6} + x_{2}^{4} z_{6} + x_{3}^{4} z_{6} + x_{4}^{4} z_{6} + x_{6}^{4} z_{6} + x_{3}^{4} z_{7} + x_{5}^{4} z_{7} + x_{6}^{4} z_{7} + x_{5}^{4} + x_{7}^{4} + x_{2}^{2} x_{3} + x_{1} x_{3}^{2} + x_{3} x_{4}^{2} + x_{4}^{3} + x_{1}^{2} x_{5} + x_{3}^{2} x_{5} + x_{1} x_{5}^{2} + x_{2} x_{5}^{2} + x_{4} x_{5}^{2} + x_{3}^{2} x_{6} + x_{4}^{2} x_{6} + x_{0} x_{6}^{2} + x_{2} x_{6}^{2} + x_{5} x_{6}^{2} + x_{0}^{2} x_{7} + x_{2}^{2} x_{7} + x_{5}^{2} x_{7} + x_{6}^{2} x_{7} + x_{0} x_{7}^{2} + x_{3} x_{7}^{2} + x_{5} x_{7}^{2} + x_{6} x_{7}^{2}\\
$$

I would assume that every exponent $\neq 0$ of any $x_i$ and $z_i$ can be ignored because those variables representent coefficients in $GF(2)$ and can be either $0$ or $1$. *

So when I ignore the exponents this looks very similar to the bi-affine equations (a sum of combinations of $x_i$ and $y_i$, sometimes with terms of only $x_i$ or $y_i$ - the only thing which is new is that there are terms of $x_i$ and $x_j$ multiplied together) and I would like to understand the difference!

So how are these equations "fully quadratic" and what does it mean exactly? What is the difference to the bi-affine equations besides the number of the equations?

*: This was also necessary in the process of generating the 23 bi-affine equations, where the equation $x^{128} = y^{128} x$ was used. This led to $x_i^{128}$ in the result which to my understanding can also be shortened to $x_i$.

Looking at appendix A of the eprint I'd say that the authors call a polynomial of algebraic degree at most $2$ bi-affine, if it contains some terms of algebraic degree $1$, and fully quadratic, if there are no such terms.

(Working over fields of characteristic $2$ the map $x\mapsto x^2$ is linear over the field with two elements and of algebraic degree $1$.)


Is the Vernam (One Time Pad) cipher useful? By profession I’m a programmer. I don’t know a lot about how cryptographic algorithms are implemented, or even where I’d start, and I don’t know about cryptanalysis, but as I work in Blockchain technology, I know how to consume cryptographic algorithms. One might say I have a passing interest.

One thing that has piqued my curiosity, as it probably does many novices in cryptography is the Vernam, or One Time Pad cipher; supposedly 100% mathematically impossible to crack and incredibly simple to implement.

The problem seems to be around the keys used. Specifically:

Keys shouldn’t be reused
Key sequences shouldn’t be repeated
Keys need to be shared somehow

Other encryption algorithms solve (or don’t suffer from) these problems, but, if we can find a suitable, secure way to generate and share unique keys, does the Vernam cipher become useful?

Is there anything else that needs consideration in this respect?

As you know, if a thing is useful or not depends upon context.  If you are hungry, will a 4096-bit RSA key with a CAMELLIA256 subkey be useful?  Not really, except perhaps as food for thought.

One-time pads are being used at this very moment by serious and perhaps dangerous people all over the world.  OTPs work.  Ciphertext encrypted with a one-time pad can be heard on HF radio all the time.  Is it useful?  Certainly.  The question is: "for whom?"

Why are one-time-pads useful?  You don't have carry around a lot of equipment.  Paper does not leave an electronic trail.  Paper burns.  Little pads are easy to hide. It's hard to get a kleptotrojan into a pencil.  Paper is cheap.  Vernam cipher is the perfect cipher if the key is truly random, the key was protected, and the key is as long as the message.  When your equipment stops working you can pull out the little book and figure out a way to deliver your message--and its content will remain private.  You can actually see the key destroyed. When you destroy it, it's really gone.  Everything about using a one-time-pad is easy to understand. A one-time pad does not require electricity. If you lose your pad, that might be bad, but you don't have to revoke it in front of everyone.  All of that sounds very useful, right?

So, to answer your question directly, "if we can find a suitable, secure way to generate and share unique keys, does the Vernam cipher become useful?"--yes, it already is very useful to certain people all over the globe, but they are not talking about it.

"Is there anything else that needs consideration in this respect?"

Yes.

It isn't that the key "should not" be used again, as if it were an option.  It must only be used once.
The key must be at least as long as the plaintext.
The key must be truly random in order to be perfect.
The key must have been protected against damage or compromise.
The key must have been shared via a secure means.


Reduced variants of stream ciphers What are "reduced variants" of stream ciphers and how do they relate to lightweight cryptography?

How do their internal states compare to those of non-reduced variants? Security aspects?

I am aware of reduced variants of Salsa20 (Salsa20/12 and Salsa20/8). These are variants of Salsa20 using reduced number of hashing rounds (12 and 8 instead of standard 20).

This is the same idea as reducing number of rounds of a block cipher - you get better performance by undermining security.


What does "Clocked" mean in alternating step generators In the wiki article, it says "An ASG comprises three linear-feedback shift registers, which we will call LFSR0, LFSR1, and LFSR2 for convenience. The output of one of the registers decides which of the other two is to be used; for instance, if LFSR2 outputs a 0, LFSR0 is clocked, and if it outputs a 1, LFSR1 is clocked instead."

I would appreciate it if someone could explain how an ASG works and what it means for the LFSR to be clocked or left alone and if possible, a small example to show this.

Clocked is an electronics term and here it applies to the LFSR's implementations;

Assume that the LFSRs are implemented with D-FLip-Flop that can store values in bits.

At each clock, the waiting input (D) passes the output (Q) and in LFSRs that go to the next cell. This is the shift operation.

The clock of the system simultaneously acts on D-fLip-flops if not controlled by some other logic. If one controls the clock with an additional logic/value as in ASG

then according to the logic, D-fLip-flop may not be clocked that result in keeping the same values. The LFSR still outputs the same value as the previous clock.

In software you can consider this like;

Have an LFSR class that hast two functions apart from the constructor, destructor, and some other utilities like the current step value;

advance() -> that shifts the LSFR and feedback the new value according to the feedback polynomial
getOutput()

According to control value, one call advance() then getOutput() or just getOutput(). The latter is keeping the previous values.


MD5: Existence of invariant (fixed point) Is it possible to find 128 bits $B$ such that $md5(B) = B$?

md5 has collisions that can be computed in acceptable time, but I did not find any papers on fixed points in md5.

As pointed out in this question from 2014, there is a 63.2% probability for a totally random hash function to have a fixed point. Since some time has passed, I would be interested in newer research into the topic of fixed points, even if the analysed algorithm is not md5 itself.

It is not known a practical method to find a 128-bit $B$ such that $\operatorname{MD5}(B)=B$. Argument: that's essentially a first-preimage attack against a variant of MD5 defined as $H(B)=\operatorname{MD5}(B)\oplus B$ restricted to $\{0,1\}^{128}$ input space, for the all-zero result; and MD5, as well as (conjecturally) that hash variant, is still strong as far as preimage attacks go.

Moreover, if we model MD5 as a random function (a natural model), the probability that there is a solution is $1-(1-2^{-128})^{(2^{128})}\ \approx\ 1-1/e\ \approx\ 63.2\%$. That leaves us far from sure that there exists a solution: odds are about 12/7.


openSSL and ECDSA key format inspection If I run openssl ec on a key that I have generated with openssl ecparam -genkey I get one extra prefixing 0x00 in the private key, and one 0x04 in the public key. While I understand the 0x04 which means uncompressed format, I don't understand the 0x00 in the private one. If I use the openssl asn1parse that 0x00 gets discarded correctly when showing the 32 bytes of the key.

read EC key
Private-Key: (256 bit)
priv:
    00:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:
    xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:
    xx:xx:xx
pub:
    04:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:
    xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:
    xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:
    xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:xx:
    xx:xx:xx:xx:xx
ASN1 OID: prime256v1

It's because how ASN.1 (DER, actually) encodes integers.

DER is not a crypto-specific format; it is a method originally designed to encode a large variety of information.  So, when they encode an integer, they provide the possibility of encoding a negative integer (even though that never comes up in crypto, it may be used in other usages).

They encode the integer as a big-endian byte string (where the first byte is the most significant one), and they use the convention that the msbit of the first byte indicates the sign of the encoded integer.

This raises an obvious question: what happens if the msbyte of the integer was, say, 0x80?  If you made that the first byte of the encoding, the decoder would see that this msbit was 1, and so would assume that the integer was negative.  To avoid this possibility, what DER mandates is that, in that case, you prepend a 0x00 byte in front.

This is what is happening; your private key is an integer that just happens to be between $2^{255}$ and $2^{256}$; because the msbit of that msbyte happens to be a 1, a 0x00 is prepended.  This will happen on about half of the private keys you'll generate.


Is a tweakable block cipher still considered deterministic in nature? "a block cipher is a deterministic algorithm operating on fixed-length groups of bits, called blocks, with an unvarying transformation that is specified by a symmetric key. - Wikipedia "

But with a native tweak support inside a block cipher, one can achieve "varying" transformation with same symmetric key but different tweak. i.e probabilistic encryption without changing the key or using the block cipher in some mode .

Now is a block cipher with native tweak support still considered a deterministic encryption ? The only determinism being the length of the output (that is same as length of the input).

When talking about encryption with block ciphers, you should distinguish block cipher itself from the mode of operation that employs the block cipher.

Block cipher takes an input $P$ of fixed length $n$ and transforms it under key $K$ (and possibly under other parameters such as tweak $T$) to output $C$ of the same length $n$:
$$
E:\; P \xrightarrow{K(,T)} C.
$$
It is always deterministic in the sense that $C$ is entirely determined by the listed parameters.

A mode of operation $\Pi$ is used to turn a fixed-length block cipher into a variable-length encryption scheme. To achieve semantic security, modes of operation typically uses deterministic nonces or random initialization vectors. In the latter case the resulting schemes are called probabilistic.

The use of tweaks is somewhat orthogonal to this classification. Both deterministic and probabilistic modes may use tweaks to further parametrize the encryption (e.g., in disk encryption).


Is the statement true in the context of AES-256 encrypted data stored on a hacked server? I'm writing a document and I am making an important statement in it, which may be used for strategic decision regarding data-management (possibly from never handling sensitive information online to allowing some to be). I am certain of that statement, however I would like encryption specialists to confirm, infirm or precise it. This is the statement:

  Important note: as long as the data on the server (name of platform) is encrypted and the decryption key safely stored elsewhere according to protocols established, it does not matter (from an access to the data perspective) if the account on the server is hacked. In that case the real protection for the data is the encryption, not the server itself, although it does act as an additional layer of security.

Context: The data is encrypted on a local device and submitted (encrypted) on to the application on the server. It is then downloaded by users (still encrypted) to be decrypted locally using the key. We are talking about AES 256 bits encryption using CFB. The statement does not concern data management by users (e.g. their handling of the key, as it does state that it assumes this is done properly) and does not concern the mobile devices used to created/encrypt/submit the data (this is addressed separately).

I am aiming at being as precise as possible (e.g. I don't want it to be generic hog-wash more aimed at protecting the writer than helping), but I want to be certain of what is written.

So the question is: Is the statement true in the context defined? If it is not or should be nuanced/modified, what should I change?

EDIT: (The reworded statement according to provided answer below):

  Important note: as long as the data on the server (name of platform)
  is encrypted and the decryption key safely stored elsewhere according
  to protocols established, it does not matter from a data confidentiality
  perspective if the account is hacked, although in that case data
  integrity is not guaranteed. The real protection for confidentiality of the data  is
  the encryption, not the server.

Important note: as long as the data on the server (name of platform) is encrypted and the decryption key safely stored elsewhere according to protocols established, it does not matter (from an access to the data perspective) if the account on the server is hacked. In that case the real protection for the data is the encryption, not the server itself, although it does act as an additional layer of security.

Yes and ... No.

Could you define what do you mean by access to the data perspective ? By whom ?

You need to have a clear definition of the properties you want to guarantee. In cryptography there are 3 essential properties.

confidentiality: only the authorized users can read the data (and understand it).

integrity: the users have the guarantee that the data have not been modified, or in other words only the authorized users can modify the data.

authenticity: the users have the guarantee that the data/entities are who they are (this is different from identification).

In the case you are talking about, you only implies that you are providing confidentiality but no integrity. In other word, an attacker could access the data, not be able to read it but could still modify it. Note also that the property access to the data perspective is not provided anymore to the authorized user in the case where the data have been modified.

Thus in my opinion, you should slightly improve the text to say that you don't provide the integrity in this case (or use an Authenticated Encryption Scheme). It might also be a good idea to use the vocabulary previously defined (confidentiality and integrity).


Do I have to transfer the private key to digitally sign a remote document? I'm trying to digitally sign a document which is uploaded by a user. I want the user to sign that document using his digital signing certificate (DSC).

Should I:

transfer the file to the user, and have them sign it on their own system, or
transfer the user's private key to the server, and sign the file there?

Which way is better, or are there any other, better ways to do this?

It is logically impossible to transfer a private key. The key will continue to be a signature key, but it will cease to be "private" the minute it is transferred. A signature key that isn't private isn't a private key. If you want the document to be signed by the user (in any semantically coherent sense), this operation has to take place on a device exclusively controlled by the user.

This doesn't mean that it is logically impossible to delegate digital signing to a third party, it just means it has to be done slightly differently. If (in real life) you appoint someone to act as your proxy, you don't authorize that person to sign documents using your signature. Instead, you sign a letter of appointment that authorizes your proxy to sign documents on your behalf. The proxy will then use its own signature.


Diffie Hellman Problem (DHP) and Discrete Logarithmic Problem (DLP) I am novice here. I am following a lecture series of Prof. Christof Paar and in his lecture of DLP, he states a fact which I did not understand at all. Can somebody please explain it better to me.I understand DLP and DHP independently.
The statement goes as follow:

"If the only way of solving the DHP requires the DLP, one would say that, the DHP is equivalent to the DLP" However this is not proven yet.

Also he says that if somebody proves it, it would be ground breaking research.

DH for reference:

  Alice takes a random $a$ and sends $g^a$ to Bob.
  Bob picks a random $b$ and sends $g^b$ to Alice.
  Both compute $g^{ab}$ Alice as $(g^b)^a$, Bob as $(g^a)^b$.

As you already explained breaking DLOG will break DH in the following way:

An attacker can e.g.

take $g^a$ and compute $a$ by solving the DLOG problem.
use $g^b$ to compute $(g^b)^a = g^{ab}$.

At this point the attacker knows the shared secret $g^{ab}$ and DH is broken.

However what about the other way around? Does breaking DH mean that we can compute DLOGs? The situation is not so clear...

Breaking DH means that the attacker is given $g, g^a, g^b$ and is able to find the shared secret $g^{ab}$.

The question is can we somehow leverage this knowledge of $g^{ab}$ to find $a$ or $b$.

If yes, DH and DLOG would be equivalent because breaking one always means breaking the other.
If no, DLOG would be strictly harder than DH because we can break DH without breaking DLOG but not the other way around.


AES - What is the advantage of a 256-bit key with a 128-bit block cipher? I'm just trying to wrap my mind around the decision to select the 128-bit Rijndael as the AES cipher, even with 192-bit and 256-bit keys. Even with a 256-bit key, you only get 2^128 possible outputs per 128-bit block, thus kind of rendering the larger key size meaningless (not to mention the weaker key schedules).

Was this a NIST oversight when standardizing AES?

(Answering this isn't urgent. I'm using libsodium, which uses Xsalsa20 + Poly1305, in most of my projects these days, but it's something I don't readily know the answer to.)

No, this isn't an oversight. AES is a block cipher, which is a keyed permutation. Now if you have a permutation of, say, three elements there are e few permutations possible:

a -> a
b -> b
c -> c

but also:

a -> b
b -> c
c -> a

and

a -> c
b -> a
c -> b

and

a -> c
b -> b
c -> a

(there should be $6$ for $3!$, the factorial of three, I won't write them all out)

Now if you look closely, there are more than 3 permutations possible. The actual number of permutations is higher than the input/output! To be precise, the number of permutations is $(2^{128})!$, which is a lot more than $2^{256}$.

The purpose of the key is to select one of the possible permutations. So the key could be a lot larger than 256 bits and still be meaningful. This also means that there may be multiple keys that map a specific ciphertext block to a specific plaintext block. An attacker may have to validate more pairs to be reasonably sure of success. For instance, in both the last two permutations in the example, a maps to c.

The block size is - as Yehuda Lindell writes in the other answer - needed when many blocks are encrypted. For instance when you choose a random nonce for CTR mode, the blocksize must be high enough or you will get overlaps in the counter that is encrypted to create the key stream (i.e. choosing a twice in the example). In that case the key stream would repeat, breaking the stream cipher.

An example of a block cipher with a much larger maximum key than block size is Blowfish, which has a block size of 64 bits and a key size of max 448 bits. Blowfish is considered deprecated by the author, Bruce Schneier. Besides other issues, the small block size is a major reason for the deprecation. Both followup ciphers, Twofish and Threefish, expand the blocksize.


If P256 ECDH shared secret contains ~128 bits of security, does using first half of the secret (= 128 bits) contain only 64 bits of security? There's this rather popular open source project (I'd rather not name it before possible responsible disclosure) that computes a P256 ECDH shared secret (256 bits) and uses only first half of it, rams it through a KDF, and uses the result as a 128-bit AES key.
I'm wondering if that's problematic regarding its security since it looks like it's trying to offer 128-bit security, but I wonder if the result is 64-bit security because even if you take 128 bits of data that has 64 bits of security (i.e. "true randomness") and pipe it through a KDF, it still has 64 bits of security?
Here's my thinking as a drawing:

Am I right in thinking they should've piped the whole shared secret through the KDF to "compress" the 256 bits to 128 bits to retain 128-bit security?
The assumptions I am running on are that P256 ECDH shared secret contains 128 bits of security, and that if you take any single byte from the shared secret, only 4 of the bits inside the byte are truly random.

First of all, generally, the shared secret is split in half because it consists of an X and Y coordinate. It is after all the point resulting in multiplying a public key point with a private key / vector, resulting in another point on the curve. Now the X and Y coordinate are related, so generally, only the X coordinate is used as a shared secret.
Currently, you are assuming that the total result is 256 bits. However, for Elliptic Curves, each coordinate of the curve is 256 bits, making a total of 512 bits. So generally you would be left with 256 bits - not 128 bits - once you split the full outcome of the ECDH key agreement. I'd make sure if that's not what is meant because it would make a whole lot more sense. Please make sure that the result is precisely 64 bytes in that case (if it is more then the header should be removed in such a way that a 64-byte X-coordinate is left - how depends on the format of the point that is generated).
Furthermore, the (classic) security of ECDH with a key size of 256 bits is 128 bits because that's what level of security finite field will produce. It is an indication of the security in bits (compared to e.g. AES) that ECDH produces. However, that doesn't mean that the X-coordinate is not well distributed; to my knowledge it is. So even if you would split the X-coordinate in half you'd still be left with 128 bits of security. Finally, even if there would be an algorithmic weakness then the one-way property of the KDF would, with a very high degree of certainty, remove such weaknesses.
All that said: if indeed 128 bits are used instead of 256 then the protocol doesn't make all that much sense. Using the full 256 bits of a (constant sized) X-coordinate should be preferred.

Notes:

I'd use AES-256 instead of AES-128 and also generate a random IV where required;
256-bit curves only provide 128-bit security against classical crypto-analysis, full-fledged quantum computers would certainly reduce that by a significant amount, rendering the algorithm insecure.


(Impossibility of?) Associative Pseudorandom Permutation I'm not sure whether this had been a long-standing open problem in cryptography.

Definition

An associative pseudorandom permutation $f(k,m)$ is a permutation such that:

$f(k_1, f(k_2, m)) = f(f(k_1, k_2), m)$
Given $s = f(k, m)$ and $k$, the only way to find $m$ is brutal-force search.
The output of $f$ is indistinguashable from random using polynomial-time algorithms.

With such a permutation, constructing key encapsulation and digital signature would be as easy as calculating 1+1. But as of 2017, the best approximation seem to be homomorphic encryption.

Question

If everyone can infer that APP is the ideal solution to PKC, then why isn't there a concrete instance of one? What are the practical difficulties and open problems standing in the way?

As mentioned by Meir Naor in the comments, what you are describing is impossible. The reason is that the associativity gives us leverage to distinguish the function from a random function. To do so an adversary $\mathcal{A}$ with access to an oracle that is either $f(k,\cdot)$ for a random key $k$ or a truly random function $g(\cdot)$ can proceed as follows:

Choose random $k'$ and $x$ and compute $y := f(k',x)$.
Query $y$ to the oracle and receive back $z$.
Query $k'$ to the oracle and receive back $k''$.
Compute $z':= f(k'',m)$ and check whether $z'=z$.
If it is output $1$, otherwise output $0$.

To see that $\mathcal{A}$ is a successful distinguisher for $f$ we want to analyse
$$\left|\Pr[\mathcal{A}^{f(k,\cdot)}(1^n)=1] - \Pr[\mathcal{A}^{g(\cdot)}(1^n)=1]\right|$$
and see that this difference is noticeably greater than $1/2$.

In the first case we have by the associativity of the function $f$ that $z=f(k,f(k',x))=f(f(k,k'),x)$. Further we have that $k'' = f(k,k')$ and thereby $z'=f(k'',x) = f(f(k,k'),x) = z$. Therefore we have $$\Pr[\mathcal{A}^{f(k,\cdot)}(1^n)=1] = 1.$$

In the second case we have that both $z$ and $k''$ are truly random independently sampled values in $\{0,1\}^n$. In particular $z'=f(k'',x)$ is some value that is distributed independently of $z$. Therefore we have that $\Pr[z=z'] = 2^{-n}$ (i.e., the probability that an independently randomly sampled $z$ takes any particular fixed value).
This means that
$$\Pr[\mathcal{A}^{g(\cdot)}(1^n)=1] = 2^{-n}$$
and we get
$$\left|\Pr[\mathcal{A}^{f(k,\cdot)}(1^n)=1] - \Pr[\mathcal{A}^{g(\cdot)}(1^n)=1]\right| = 1-2^{-n}$$
which is noticeably greater than $1/2$. (In fact it's only negligibly smaller than $1$.)

This shows that any fixed associative function is always distinguishable from a random function. Also note that this attack does not go away by just constraining $g$ to be a random associative function. This is because we are not simply checking whether the oracle is associative. We are specifically using the associativity of $f$ to check whether the oracle is $f$. In the case where $g$ is associative, the analysis gets a bit more complicated because $z$ and $z'$ are now no longer completely independent. But the attack still works.


ElGamal and Pailler combined currently I am working on some secure accounting application. I have few requirements:

Application should store items which can be searched by name.
Every item has price and tax.
Every invoice contains arbitrary amount of different items.
Every invoice has gross and net sum of items

My idea is to use rsa or ElGamal schema for multiplication and Pailler for addition. Calculating net sum is pretty easy I can just use pailler for doing it. Problem is with gross sum. In my solution for each item I am doing multiplication: price*tax using RSA and here I am stucked.
I have only one solution in my mind: adding another trusted proxy to my system which will receive result of each multiplication, decrypt it and encrypt using Pailler scheme and than send it back to my server (which now can sum gross values of each item). That solution requires a lot of communication between server and proxy and client has to give his private keys to the proxy. Do you have any idea how can I improve it?
Thanks in advance!

There exist methods which allow to switch between a multiplicatively homomorphic encryption scheme - such as ElGamal - and an additively homomorphic encryption scheme - such as Paillier. By switch, I mean securely converting an encryption of a plaintext under one scheme into an encryption of the same plaintext under the other scheme. This is precisely what we described in this paper (see also the follow up). In these works, no proxy knows the full secret key of either scheme: the server and the proxy only have to know shares of the private keys of the scheme (hence, neither the server nor the proxy can decrypt any ciphertext alone).
Several important remarks, however:

In your question, you seem to completely ignore one of the most crucial aspects: the additive and multiplicative schemes must be compatible, in the sense that they must (essentially) operate over the same structure. By default, RSA is multiplicative over $\mathbb{Z}_n^*$ and Paillier is additive over $\mathbb{Z}_n$. These rings do not even have the same order, and this is extremely problematic - it can be easily used by an attacker to completely destroy security. Solving this issue is actually one of the main hard steps in our paper.
RSA is not secure for your application. It is only one-way; you cannot hide a money amount with a one-way scheme, since there are not so many possible values. An attacker could try to encrypt all possible amounts to learn which one was encrypted.
Is "tax" supposed to remain secret? I do not see why it should be a secret value in your application, since tax is typically public. If tax is public, you do not need any multiplicative scheme whatsoever: Paillier already allows to compute operations of the form $\sum_i \alpha_i \cdot m_i$ given encrypted plaintexts $m_i$ and arbitrary public coefficients $\alpha_i$.
In any case, if you need to do a single multiplication (or several "single multiplications" in parallel), like $\sum_i \alpha_i \cdot m_i$ (and not e.g. $\prod_{i=1}^n m_i$ for a large $n$), I would advise against using any technique for switching between encryption schemes. It will considerably complexify the construction, make it very hard to analyze and error prone, and it seems completely unnecessary. There are secure two-party protocols to securely compute, given Paillier encryptions of $x$ and $y$ respectively, a Paillier encryption of $x\cdot y$, where the two parties have shares of the secret Paillier ket (i.e. no one holds the full key). Roughly, it goes as follows: Alice picks a random mask $r$ and computes $E(x+r)$ ($E$ is Paillier encryption), the parties jointly decrypt such that Bob gets the plaintext $x+r$, and computes $E(y\cdot (x+r))$ from $x+r$ and $E(y)$. Bob sends back this ciphertext to Alice, who can herself compute $E(y\cdot r)$ (since she has $r$), and homomorphically substract the ciphertexts, getting $E(x\cdot y)$. This is a simple standard protocol to interactively multiply Paillier encrypted values.


Is it worth hiding an AES encrypted text string in a PNG image for better security? I need advice as to whether it is worth the extra "security" and processing of an AES encrypted text string to be hidden in a PNG image as opposed to an AES encrypted text string to be saved in a read-only text file. Both the PNG image and Text file would serve as publicly available AES placeholders that would be decoded via password in a web application. I gather that any hex editor or similar software could access the AES string anyhow, so, would there be any practical benefit security-wise in hiding the AES string in a PNG?

"Hiding" content in an image (or other medium, it's a general technique called steganography) can be done either in a very obvious way (a dedicated data block, called ancillary chunk, which does not form part of the image), or it can be more effectively hidden in the low order bits of the image, thus very subtly degrading the picture.

Both methods can be discovered by a dedicated analyst, there are even automated tools which can flag images if some telltale statistical anomalies are detected.

This method doesn't add any extra security for the secret message - which is already encrypted anyway. The only thing it provides is a very weak protection of the fact that a secret message existed at all.


Can I use PBKDF2 for authentication and decryption? I want to store a hash for authenticating a password.  I also want to use the same password for decryption.  Can I use PBKDF2 for both?  (I plan to use different salts for the authentication and the decryption, of course, because otherwise the authentication result would be the decryption key!)

Is that appropriate/secure?

It's fine, as others have noted.

However, by invoking PBKDF2 twice (first to check the password, then to derive the actual key), you're essentially doubling a legitimate user's workload, whereas an attacker still only needs to run it once for each guessed password.  Thus, you're cutting the legitimate user's advantage in half, or, equivalently, wasting one bit of password entropy.

(Also, the way PBKDF2 is defined, deriving more than one hash output length of key material is basically equivalent to invoking the whole PBKDF2 function two or more times, so you won't gain much that way.  Other KDFs like scrypt may behave differently in this respect.)

Instead, I would recommend deriving a single "intermediate key" $K_I$ from the password $P$, using PBKDF2 with a suitably high iteration count, and then deriving both the password verification value $V$ and the actual encryption key $K_E$ from the intermediate key using a fast KDF (e.g. PBKDF2 with an iteration count of 1), like this:

$$\begin{aligned}
K_I &= \text{PBKDF2}(P,S,c,\max(\ell_P,\ell_V,\ell_{K_E})) \\
V \,\|\, K_E &= \text{PBKDF2}(K_I,S,1,\ell_V+\ell_{K_E})
\end{aligned}$$

where $S$ is the salt, $c$ is the iteration count, $\ell_P$ is the output length (in bytes) of the PRF used to instantiate PBKDF2, and $\ell_V$ and $\ell_{K_E}$ are the desired byte lengths of the verification token $V$ and the encryption key $K_E$ respectively, and $\|$ denotes their concatenation.

(The reason for choosing the intermediate key length as $\max(\ell_P,\ell_V,\ell_{K_E})$ is that we want the intermediate key to be at least as long as each of the final outputs $V$ and $K_E$, and there's no point in asking for output shorter than what the PRF naturally gives us; in fact, an even better choice could be $\max(\ell_V,\ell_{K_E})$ rounded up to the next multiple of $\ell_P$.)


Is the following authentication protocol insecure? I am a student taking cryptography this semester. I was just wondering why can't we use this simple protocol?

Alice → Open Connection → Bob
Alice ← Cert$_b$ ← Bob
Alice → {K$_{AB}$}$_{Bob}$ → Bob

Assume bob is the server and we're only interested in one way authentication.
Is there anything wrong with it in terms of security and performance?

Bob needs proof that Alice is authentic:
A-Open Connection-Cert partial random key->B Both keys combine to form an access key.

Standard one-way authentication protocol only requires submitting a correct password once, in order to gain access and control. By randomizing part of Alice's password, significantly reduces the likelihood of her password becoming victim of replay attacks and man-in-the-middle-attacks, just to name a few. [Random Assymetric] Bob's server has been preset for random variations of Alice's hash value

Is there anything wrong with it in terms of security and performance?

Technically speaking, there is nothing wrong with your suggested one-way authentication protocol. However, the security function of your protocol can be increased by preconfiguring Bob's server with random hash variations of Alice's password for added security. Best of luck with your protocol


How realistic is a dictionary attack on a secure remote password protocol (SRP) verifier? I'm deploying a secure remote password protocol implementation and I'm wondering what the consequences are when the client generated verifier gets leaked to an attacker.  I've read Thomas Wu's paper and as nice as it is, it doesn't talk about that scenario.  I also read RFC 5054 and it has the assertion:

  If an attacker learns a user's SRP verifier (e.g., by gaining access to a server's password file), the attacker can masquerade as the real server to that user, and can also attempt a dictionary attack to recover that user's password.

If the client is using the verifier as assurance of the server's identity, I can see how that would go badly.  It's the second assertion of a dictionary attack that makes me wonder.

x = H(s, P)
v = g^x mod n

How much effort would it take to solve for P without knowing x?  It seems like the implied mod of n totally obscures x.  And then, there should be many values of P that could generate a v, but a much smaller set that would pass the verification stage.

And if a dictionary attack could find the password, how is this better than a shared secret protocol?  Is the dictionary attack mentioned in the RFC just saying "if I had an infinite speed computer I could really ruin your day?"  Or does it mean it could run a dictionary attack on the client while pretending to be the server?

The security goal behind SRP is that an attacker that could either pretend to be a client (and attempt to log into a server that knows the key), pretend to be a server (and allow clients that know the key to attempt to log in), or actively monitor (and modify) the communications between a valid client and a valid server, would learn nothing from an exchange, except possibly whether a single password is valid or not.  This last bit cannot be helped with a password-based authentication method, as the attacker could always take his guess at the password, and then proceed with the protocol with a valid server or client, and see if it succeeds.  The point of SRP is that the attacker can't do any better than that.

Now, in the protocol, the value v is never sent over the wire, and so the attacker does not see it, and so a dictionary attack against that value is impossible (unless the attacker can rederive that value somehow, which is not believed to be possible).

On the other hand, the note you highlighted assumes that the attacker can do more than just work with the protocol; it assumes that he is also able to access the password files on the server.  If he can do that, well, yes, he knows enough to impersonate a server, and he can also perform a dictionary attack on the password; namely for each password P' in his dictionary, he computes:

x' = H(s, P')
v' = g^x'

and check if v == v' (note: it is quite unlikely that you could stumble on a different password that also passes this check)

Note that this is not specific to SRP; for any password-based authentication method, if the attacker can learn everything the server knows, then he can impersonate the server, and in addition, he can perform an undetectable dictionary attack (for example, by simulating a client logging in with various passwords; this is undetectable because since this occurs entirely on the attackers equipment, you aren't informed that someone that someone is trying to log into the system with a long series of passwords).

As for why this is better than a shared secret protocol, well, an attacker can run a dictionary attack even if he didn't have direct access to the server's password files; with SRP, that sort of access is needed.


Given p and q of DSA how do you show they are prime? I am given

p = 4916335901
q = 88903

and am asked to show these are prime as well as q|(p-1) in DSA.

I am unsure on how to do this, what does q|(p-1) mean exactly?

I am given $p = 4916335901$, $q = 88903$ and am asked to show these are prime

To check whether a given integer $n$ is prime you have to check whether it is only divisible by $1$ and $n$, i.e., that it is not a composite integer. If you are given such an integer you can either factor the given integer, use primality tests to check for primality or in case of such small numbers just ask Wolfram alpha. In your case, both $p$ and $q$ are indeed prime, and your given $p$ is of the form $p=k\cdot q +1$. Most often one encounters the use of $k=2$, so called safe primes in cryptography. You can generate such primes even in the size for cryptographic purposes efficiently.

  as well as $q|(p-1)$ in DSA.

The notation $a|b$ means that $a$ evenly divides $b$, i.e., $b$ divided by $a$ gives a remainder of zero. This is easy to check by computing $\frac{4916335901-1}{88903}=55300$, so yes $q|(p-1)$.

Using a prime of the form $p=k\cdot q+1$ with small $k$, you know that when you are working in ${\mathbb Z}_p^*$ (which has order $p-1$) that you have a cyclic subgroup of prime order $q$.