Why is EAX not a generic composition? In the document http://web.cs.ucdavis.edu/~rogaway/papers/eax.pdf (p. 7) Rogaway et. al. state that EAX is not a generic composition of an encryption and an authentication method.

The EAX algorithm is given in the following Image:

(the image is taken from p. 7 of the referenced paper and simplified by omitting the associated data)

So, the plaintext M is encrypted by a CTR block cipher mode and the resulting ciphertext is authenticated by an OMAC tag. So far, this looks pretty much  like an encrypt-then-authenticate based generic composition. The only thing particular here is, that the tag $\mathcal{C}$ isn't the final tag but is XORed by the tagged nonce $\mathcal{N}$.

My questions are:

Why isn't EAX considered to be a generic composition ?
Would EAX be a generic composition of the block cipher mode encrytion and the OMAC authentication, if $\mathcal{C}$ would be used as authentication tag T ?

Added: Actually, I think the answer depends on the point of view.

(1) Proof of security: Security proofs for generic compositions assume that two different, independet keys are used for encryption and authentication. As EAX uses the same key for both, security results for generic compositions don't apply to EAX. So in this point of view EAX is not a generic composition.

(2) Design principle: When one tries to classify AE algorithms, one can look how they are designed. By design, a generic composition is an algorithm that runs an encryption and an authentication algorithm in a (generic) order that is independent from the primitives: E.g. Encrypt-then-Authenticate, Authenticate-then-Encrypt, etc. In this point of view I would consider EAX (as well as CCM) as a generic composition.

When reading the paper, it seems that there are three or so properties that make a generic authenticated encryption method:

a generic encryption method and MAC are used;
two different keys are used for both;
two pass encryption is used (generally encrypt-than-MAC).

EAX uses two well defined algorithms: AES and CMAC. So it seems the definition fails on (1). As EAX uses only 1 key it will always fail on (2) as well.

But yes, if you do not consider the special way $\mathcal{N}$ is constructed then EAX outputting just $\mathcal{C}$ could be considered a relatively generic construction when it comes to (3).

Adding it up, I personally think this should be a big NO, EAX is not a generic construction as defined in the paper; and just outputting $\mathcal{C}$ only makes a tiny difference.


What security flaw exists in MAC authentication scenario? What security flaw exists (if any) in the solution of this non-encrypted authentication scenario?

An unencrypted message passes one-way from computer A to B. Its transmission is viewable by the public. The message does not need to be kept secret. Both A & B have already securely exchanged any needed keys. A and B keep their keys secret.

Goal:

B needs to authenticate that the message (10s to 1000s bytes) originated from A.
Prevent others from creating a message (other than a copy that A originated) that B would mistake for an authentic message.

Solution (MAC)

A appends a MAC to the message and sends it. B receives purported message and MAC.
B authenticates (or not) the message/MAC. MAC size: about 256 to 512 bits.

Looked over other Q&A, but authentication is so often tied with confidentiality that I failed to find posts that addressed authenticity without a secrecy requirement.

[Edit]

I selected the answer (1 of 2 good answers) that presented the original scenario’s biggest problem: Via comments, it came out that $B$ is really a set of clone $B$s and thus a MAC does not authenticate that the message came from $A$ as it could come from another $B$.  Thus warranting a Digital Signature.

The following points shift the nature of the question but do align with the realities of my particular situation.  There are mentioned here should additional answers wish to address the modifications - which I will review and likely up vote.  I should post a new more clarified question later.

A1. My 1st goal s/b “$B$ needs to authenticate that the message (10s to 1000s bytes) originated from $A$ or from another $B$.”  Thus a MAC appears still OK.

A2. Non-repudiation of a message is not needed.

A3. Each message is complete and is not part of a larger message set (ordering or selective blocking not an issue.)

A4. The size of the MAC (or alternatives) is limited.

Details: There is no wired network.  The messages & MAC are contained in RFID tags.  The message describes a product attached to an RFID tag.  These messages are generated by $A$ "the factory" and distributed, via public means, to various $B$s.  A given machine $B$ may alter the message either with the original MAC or with a new MAC unique to that $B$ machine - TBD.  The product need not move between the clone $B$s.  All this does not authenticate a valid product exists (the product and RFID tag could be separated or the RFID is spoofed). It does authenticate that a valid product’s message exists.

Digital signatures are used to solve this type of problem. That is, a way for $A$ to sign the message for $B$ so that $B$ is highly confident that $A$ signed the message in question. There are lots of signature schemes out there, such as RSA signing, DSA, and others.

A MAC is not strictly a digital signature, but has a subset of that functionality and may meet your stated goals. It meets the requirement that an attacker won't be able to forge a new MAC without the key, which was the second point listed. (See this tangentially related question about HMAC.)

However, a MAC doesn't strictly meet the first stated goal. The problem is that MACs are based on symmetric keys, which means that everyone with the key can "MAC-sign" a message. When verifying a MAC, all the receiver ($B$) knows is that one of the parties with the symmetric key "signed" the message, but it don't know which one did. A copy of $B$ may send MAC-signed messages to other copies of $B$ and nothing distinguishes those MAC-signings from $A$'s MAC-signings. Practically speaking, this means, at a minimum, the attack surface of which compromised hosts can impersonate $A$ is widened. You no longer have to trick $A$ into signing malicious plaintext in order to forge $A$'s MAC-signature (such as by hacking it), using copy of $B$ will suffice.

This can have horrible implications if messages from $A$ are audited later and need to be verified as originating $A$ under the assumption of foul play on the network. (Maybe a legal court audit, perhaps just verifying that data collected was collected at $A$, etc.) Since any $B$ can forge a message on $A$'s behalf, you can't prove $A$ sent the messages. However, this may or may not be a concern for you.


Key derivation using known parameters of playfair Is it possible to derive the key, for a playfair cipher, if both the message and cipher text are known?

There are two issues to be aware of.
Firstly if the message and cipher text are short, or lack variation in the usage of letters, there may not be enough information to recover a complete Playfair square,
Secondly, rotating all the rows or all the columns of a Playfair square gives an alternative square that encrypts in the same manner. Thus squares come in families of 25. If the “key” is a word or phrase, it is usually straightforward to recover the key used by the system. If the key is a “random” arrangement of 25 letters, then the precise key cannot be distinguished from the other 24 without more information.
If you're asking about the process for recovering the square given matched plain and cipher, this can be done manually and is relatively straightforward. Consider a common letter such as "E" and select all digraphs involving this letter. There are only 5 letters that can replace our chosen letter: the four with which it shares a row and the one directly beneath it. Suppose then we find that we find "E" can be encoded only as one of "ADFLX", now choose a common one of these an examine digraphs. For example we might find that "A" can only be encoded as "BEFLX", we can now conclude that one row contains the letters "AEFLX" and that "D" and "B" lie directly below "A" and "E" respectively. Now consider the letters apart from "ADFLX" that appear in digraphs with "E", within those digraphs these letters can only be encoded as either a letter that lies in the same column as "E", or a letter directly to the right. The ones encrypted to the right will share a column with "E" and "E" will be encoded to the same letter for each of these. These rules should allow you to reconstruct rows and columns of the square. The order of the rows and columns can only be inferred from encryptions of digraphs that share a row/column.


Non-interactive public sum of private values Suppose there is a large number of participants each with a secret value. The secret values are very large (e.g. 256-bit integers). Each participant has published a public commitment to their secret value.

Is it possible for them to determine what their values sum up to in a single round of communication but without revealing their private values?

This can also be thought of as a voting scheme: each participant holds a value with which they can vote. Knowing public commitments for the votes that have been cast, we'd like to figure out the total number of votes that was cast without the need for voters to collaborate with each other (beyond casting of the original vote).

If all the participants have a random secret key which sums to 0. They can each post the sum of their key with their number. Anyone can then some the values posted, the key will cancel out and we what will remain is the sum.

This only works if everybody posts their value and we have an appropriate key distributed.


Bit commitment with 1-out-of-2 oblivious transfer I know a protocol for bit commitment using regular OT (Bob has 1/2

chance of learning the bit Alice transferred to him) which goes like this:

  COMMITMENT PHASE
  Alice chooses a bit $b$
  For $i=0$ to $i=n^2$
  $\;\;\;$Alice chooses $x_{ij}$ for $1\leq j\leq n^2$ randomly so that $(\sum_jx_{ij}) \equiv b \pmod 2$
  $\;\;\;$Alice and Bob do an oblivious transfer $OT(x_{ij}=y_{ij})$ for every $j$

  REVEAL PHASE
  Alice sends to Bob committed bit $b$ and all of the $x_{ij}$.
  If $(\sum_jx_{ij}) \not\equiv b \pmod 2$ for one $i$, Bob rejects. Otherwise, he accepts.

So this protocol uses $n^2$ iterations of OT. I'm trying to find a protocol that would use instead $n$

iterations of $\binom{1}{2}-OT$ (1-out-of-2 oblivious transfer) with exponential security in $n$. I'm thinking

about using $xor$'s and random bits but the only way I can think about has linear security (I think) ...

  COMMITMENT PHASE
  Alice chooses $b$ and $2n$ random bits $\{b_1,b_2,\dots,b_{2n}\}$

  such that $b_1\oplus b_2=b$, $b_3\oplus b_4=b$, $\dots,b_{2n-1}\oplus b_{2n}=b$.
  Bob chooses bits $c_1,\dots, c_n$.
  Alice and Bob do a $\binom{1}{2}-OT$ for every $\{b_1,b_2,c_1\},\{b_3,b_4,c_2\},\dots,\{b_{2n-1},b_{2n},c_n\}$.
  REVEAL PHASE
  Alice sends to Bob committed bit $b$ and all of the $b_i\in b_{2n}$.
  Bob checks if $b_1\oplus b_2=b$, $b_3\oplus b_4=b$, $\dots,b_{2n-1}\oplus b_{2n}=b$.

  If it fails once, he rejects, otherwise he accepts.

I would like some of your inputs to know if I'm heading in the right direction.

It turned out that the protocol I designed was good.

Bob can't cheat because its impossible for him to discover $b$ because at every $\binom{1}{2}-OT$ iterations, Bob can only discover $b_i$ or $b_{i+1}$ for $i\geq1$ and $i=2k-1$ such that $1\leq k\leq\frac{n}{2}$ ($i$ is uneven).

Alice has an exponentially small chance to cheat without getting caught because if she would like to do so, Alice would have to lie on the reveal phase for every row for one of the $b_i$ or $b_{i+1}$, hoping that Bob discovered the other one. (She doesn't know which one Bob discovered). If Bob finds out that one of the bit isn't the one he discovered during the oblivious transfer or that one row doesn't equal the others, Bob rejects.


Unable to understand hash function representations I have some hash function representations, which I find it hard to understand.

I have searched a lot but didn't found anything helpful. Please help me understand the hash function representations given below:

  Choose cryptographic hash functions
  $H_1:\{0, 1\}^*\times\mathbb Z^∗_p\to\mathbb Z^∗_q$
  $H_2:\{0, 1\}^*\times\mathbb Z^*_p\times\mathbb Z^*_p\to\mathbb Z^*_q$
  $H_3:\{0, 1\}^*\to\mathbb Z^*_q$
  $H_4:\mathbb Z^*_p\to\{0, 1\}^{n+k_0}$
  $H_5:\mathbb Z^*_p\to\{0, 1\}^{n+k_0}$
  $H_6:\mathbb Z^*_p\times\{0, 1\}^{n+k_0}\times\mathbb Z^*_p\times\{0, 1\}^{n+k_0}\to\mathbb Z^∗_q$

I saw this from this paper
An Efficient Certificateless Encryption for Secure Data Sharing in Public Clouds (pdf, see section 2.3).

I'll review the standard mathematical notations used for $H_1:\{0,1\}^*\times\mathbb Z_p^∗\to\mathbb Z_q^∗$ , going from the bottom up. Hopefully, that will make the rest evident.

$\{0,1\}$ is the set with the two elements $0$ and $1$, known as Booleans.

$\{0,1\}^k$ (for some non-negative integer $k$ ) is the set of tuples with $k$ Booleans, or equivalently of $k$-bit bitstrings; it has $2^k$ elements. For example $\{0, 1\}^3$ (or equivalently, $\{0, 1\}\times\{0, 1\}\times\{0, 1\}$ ) is the set of all three-bit bitstrings: $\{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)\}$.

$\{0,1\}^*$ is the union of all $\{0, 1\}^k$ for all non-negative integers $k$, or equivalently the (infinite) set of all finite bitstrings. This set usually also includes the empty string.

$\mathbb Z$ is the set of (signed) integers. $(\mathbb Z,+,\cdot)$ is the (infinite) ring of integers.

$\mathbb Z_p$ (also denoted $\mathbb Z/p\mathbb Z$, especially in number theory which uses the notation $\mathbb Z_p$ for $p$-adic numbers) is the set of the equivalence classes of the equivalence relation "congruent modulo $p$" over $\mathbb Z$; that is, an element of $\mathbb Z_p$ is a maximal subset of $\mathbb Z$ such that the difference of any two elements in that subset is a multiple of $p$. By taking the smallest non-negative integer in each such subset (which also is the remainder of the Euclidean division by $p$ of any element of such subset), we can assimilate $\mathbb Z_p$ to the set of the $p$ non-negative integers less than $p$. $(\mathbb Z_p,+,\cdot)$ is the (finite) ring of integers modulo $p$.

$\mathbb Z_p^*$ is the subset of elements of $\mathbb Z_p$ (containing elements) having a multiplicative inverse in the ring $(\mathbb Z_p,+,\cdot)$, or equivalently coprime with $p$. An alternative definition is that $\mathbb Z_p^*$ is the maximal subset of $\mathbb Z_p$ making $(\mathbb Z_p^*,\cdot)$ a (finite) group. When $p$ is prime, $\mathbb Z_p^*$ is (assimilable to) the set of the $p-1$ positive integers less than $p$, and $(\mathbb Z_p,+,\cdot)$ is the (finite) field of integers modulo $p$.

$\{0,1\}^*\times\mathbb Z_p^∗$ is the set of (ordered) pairs with the first element of the pair in $\{0,1\}^*$ and the second element in $Z_p^∗$.

$H_1:\{0,1\}^*\times\mathbb Z_p^∗\to\mathbb Z_q^∗$ is a notation stating that $H_1$ is a function from the set $\{0,1\}^*\times\mathbb Z_p^∗$ to the set $\mathbb Z_q^∗$. That is, $H_1$ takes as input a bitstring $b$ of unspecified (but finite) length (possibly the empty bitstring), and an integer $i$ coprime with $p$ and defined modulo $p$ (that is, $i$ and $i+z\cdot p$ are assimilated and will produce the same result for all $z$ in $\mathbb Z$ ), and produces $j=H_1(b,i)$ coprime with $q$ and defined modulo $q$ (we can think of $j$ as a positive integer less than $q$ and coprime with $q$, or as the set of all integers having that remainder by the Euclidean division by $q$ ).


Correlation power analysis attack on Camellia I'm investigating a correlation power analysis on a black-box ASIC I have.
I want to learn about correlation analysis and it seems this ASIC implements Camellia.

I searched for researches that did CPA on Camellia but it seems no-body did it.

I have 2 questions.
1. why ? is this algorithm resilient to CPA ? if it is then why ?
2. If it does not, which correlation should I search for ? this algorithm is not intuitive like AES ... and also I dont really know that this is camellia. only that this is not AES :)

Also,
I assume Camellia since I saw 18 repetitive struct ... maybe 18 rounds ?

Camellia is 128-bit  Feistel block cipher and 128/192/256 key. The sbox is 8-bit register, hence there are 8 cells in F function . The correlation power analysis depended on hamming weight. Steps to be taken:

1. Build a matrix of all possible keys (256) on each cell, the matrix
size is 8*256=2048, then calculate the hamming weight ( I guess for
hardware implementation , the model is hamming distance)
2.  Collect power consumption traces during encryption process, the number of traces differ from experiment to other but usually range
up to 10000 traces.
3.   Calculate the correlation between the model and traces.
4.  the best coefficient indicates the possible correct key.
5.  To obtain the 128 key , you need to do the correlation for two rounds (first and second) since the sub key size is 64 bit , the
same applies for 192 (three rounds) and 256 (four rounds)

To answer your questions:

1.  Is this algorithm resilient to CPA ?

Non-masked implementation of cipher can be attacked by correlation power analysis.The implementation of the cipher plays a factor, Camellia has 4 8-bit sboxes , the cost of countermeasures implementation against CPA is high but securing against CPA , it does not mean it is secure against other types of Side channel attacks.

2.   If it does not, which correlation should I search for ? this algorithm is not intuitive like AES .

If I understand what you meants , the correlation is pearson , I think this
link might help you.


Diffie Hellman unsafe prime vulnerability I have done some research about how the DH key exchange is unsafe if an unsafe prime p is used (that is, $p-1$ has a lot of small factors). Many answers here on StackExchange claim that for any factor $r$ where $g^{\frac{p-1}{r}}\neq1$, if given $g$ and $g^x \bmod p$, one can determine the value of $x \bmod r$ in $O(\sqrt{r})$ time (See this and this answer).

The latter of the two answers even includes an outline of a way to do this. However, this requires $A^{\frac{p-1}{r}}$ with $A$ being the public key to be calculated. For a large $A$ and $p$ (say 4096 bits for both) and a small $r$ (8 bits or less), for me this does not seem to be computationally possible. Therefore, I was wondering how one would write a solution to this problem which is possible to execute with finite time and memory.

For a large $A$ and $p$ (say 4096 bits for both) and a small $r$ (8 bits or less), for me this does not seem to be computationally possible.

Actually, it's straightforward to compute $A^{\frac{p-1}{r}} \bmod p$; one straightforward way is to use the binary exponentiation algorithm.

If $\frac{p-1}{r} < 2^n$, then this will take no more than $2n$ modular multiplications (and so, in your example, fewer than 8184 modular multiplications); one could do somewhat better, but this is good enough to show that it is practical.

Note: you use those same algorithms to make the computations within DH (computing $g^x \bmod p$ for large $x$) feasible.

Note on the notation (which might be what is confusing you): sometimes, we leave off the $\bmod p$; at those times, we assume that the reader will understand that we are not working in $\mathbb{Z}$, but instead in the field $\mathbb{Z}/p$, and hence the $\bmod p$ operations are implicit.  This is similar to how, in other branches of math, you are assumed to know whether we're working in $\mathbb{Z}$ or $\mathbb{R}$ or $\mathbb{C}$...


Self signed certificate for mobile app and backend from same company My company's product is Android and iOS mobile app which connects to our own backend. All interactions of the mobile app are with backend developed by our own company.

In such a situation, can the backend use a self signed certificate (instead of getting a certificate from CA) and pin this self-signed certificate on mobile app to make it more secure.

Please let me know if this strategy makes sense (or we still have to get SSL cert from a CA)

Yes, this (certificate pinning) is the preferred method, since it removes the reliance on external authorities and makes man in the middle attacks even harder.

An additional step would be to obscure the pinned certificate inside the application to stop it easily being edited.


One-time digital signatures Are there digital signatures for which, given two documents signed by the same key, one could derive the key?

With such one-time signatures, one may be able to design a cryptocurrency based on proof-of-stake instead of proof-of-work. To disincentivise miners from cheating by mining several blocks, one could impose that miners sign with a one-time digital signature the blocks they mine. That way, if a miner did mine two different blocks with the same key, the key would be exposed and they would lose the funds associated with that key.

Yes, there does happen to be such a scheme: the Lamport one-time digital signature.

The basic idea of a Lamport signature is that the private key consists of a large number (say, 256) of pairs of secret random numbers, while the public key consists of the cryptographic hashes of those numbers.  To sign a message, you first hash it down to 256 bits, and then, for each of those bits, reveal one of the secret numbers in each pair depending on the corresponding bit.  Thus, a Lamport signature is literally a (pseudo-randomly chosen) half of the private key.

Technically, publishing two Lamport signatures using the same key weakens the security of the scheme by half, such that the probability of an attacker being able to successfully forge a signature for a given message increases from, say, $1/2^{256}$ to $1/2^{128}$.  A third signature using the same key would increase the probability of a successful forgery to $1/2^{64}$, a fourth to $1/2^{32}$, and so on.

Generally, this one-time nature of Lamport signatures is seen as a problem, and there are various signature schemes, such as Merkle signatures, that extend the Lamport scheme to work around it.  If you wanted to make deliberate use of it, you'd have to deal with the fact that, as described above, the security collapse caused by a duplicate Lamport signature is not quite immediately, but somewhat gradual.

For example, if you wanted a duplicate signature to allow easy forgery with $2^{32}$ effort, you'd have to accept that even a single signature could be forged with $2^{64}$ effort, which might be a bit too low for comfort.

One possible solution to this problem would be to modify the Lamport scheme so that, instead of pairs of random numbers, your private key would consist of, say, groups of 16 random numbers, out of each of which you'd reveal all but one in the signature (with the one hidden number in each group chosen based on four bits of the message hash).  Thus, a duplicate signature would have a $15/16$ chance of fully revealing each group in your private key (and thus rendering it trivially forgeable), increasing the forgery probability from, say, a negligible $1/16^{64} = 1/2^{256}$ to an easy $1/16^\frac{64}{16} = 1/16^{4} = 1/2^{16}$.

Of course, you'd also need to deal with all the other inconvenient features of the Lamport signature scheme, like the enormous size of the public and private keys and the signatures themselves, or the fact that, as one would expect of a one-time signature scheme, each key can indeed only be safely used once.  As the Wikipedia articles I've linked to note, various tricks do exist to mitigate several of these issues (and sometimes even several of them at once), but turning the basic Lamport scheme into something practically usable is still not exactly a trivial task.


Compare RFC 5246 SessionID re-use versus RFC 5077 Session Resumption? Can you help me understand the differences, both algorithmic and practical, between RFC 5246 SessionID re-use and RFC 5077 Session Resumption?

Both appear to be ways to nail up a second TLS session without a Server certificate exchange, leveraging the full certificate exchange and validation of a previous, separate TLS session.

Having read RFC 5246 § 7.4.1.2 and RFC 5077 § 3, it seems that RFC 5077 hands a token to the client which has session setup information encrypted with the server's key, such that the client can hand the token back to the server and shortcut the negotiation and agreement of session setup parameters.  RFC 5246, on the other hand, simply provides a reference to an existing connection that both parties share, and allows them to re-use those session parameters, based on both parties still having them in memory for the original session.

Is that a proper theoretical grasp?

Insofar as that's "close enough for government work", I'm interested in the real-world usage of the two separate types of connections:

Is RFC 5246 SessionID good

Only as long as the original session is still active?
As long as there's a consecutive chain of sessions using the same SessionID?
For a loosely defined amount of time after all such sessions have closed but before the SessionID is dropped from active memory?

Is RFC 5077 Session Resumption

Commonly used instead of RFC 5246 SessionID?
Commonly used for more widely separated connections that RFC 5246?
Commonly used at all?

Do the two differ as described here:

RFC 5077 token creation (server send to client) is wholly contained within encrypted packets, e.g., after the handshake?
RFC 5246 session exchange is wholly unencrypted, e.g., within the early (ClientHello, ServerHello) parts of the handshake?

Any insight you can share is appreciated!

UPDATE: the below was valid through TLS 1.2. TLS1.3 in 2018 changes this radically; both the old resumption and old optional ticket mechanisms are gone. Instead there is an option for both ends to store (like old resumption) a secret plus some attributes, but instead of the prior session's master secret this stored secret is now a 'pre-shared key' (PSK) one-way derived from the prior session, so that a compromise of the stored PSK does not compromise the prior session. The server uses the 'New Ticket' message type defined for 5077, but now it contains only an identifier not an actual ticket. The new session can use this PSK either directly as the 'input' secret, or to authenticate a new keyexchange using DHE or ECDHE, in the same way it can (and 1.2 and lower already could) for a manually configured PSK -- except that manual PSK always was and I expect still will be extremely rare. In addition renegotiation is now gone -- although specific operations to do client-auth and to renew the working (symmetric) keys are added -- so session and connection now are basically the same.

Yes, you have the basic idea. Session-id info is stored (cached) at both ends; ticket is stored only at client, encrypted by server. Both re-use the "key exchange" which in SSL/TLS is actually key exchange combined with authentication; although authentication can be both directions (server and client) and thus an "exchange" of certs, it is usually server-only.
To be clear on the details, you need to distinguish session and connection. A SSL/TLS session is basically the results of a full handshake: the negotiated version, ciphersuite, and (most importantly) master secret, and perhaps some other bits. This plus nonces is the data needed to correctly do encryption and HMAC, or in TLSv1.2 optionally the "authenticated encryption" modes GCM or CCM instead. A connection is coterminous with a TCP connection, and starts with an initial handshake to either create and use a new session, or resume an existing session. Resumption can be used on connections at different times within some window, or multiple connections at the same time -- most if not all browsers will open maybe 4 to 10 parallel connections to download the 10s or 100s of resources used on most(?) webpages now. It is also possible but rarer to have multiple sessions on one connection using renegotiation, usually to authenticate differently or to rekey a long-lived connection. (Well, possible unless the server disables renegotiation as a clumsy defense against the MitM-prefix attack for which the proper fix is rfc 5746.)
Session-id has been in the base protocols since SSLv3 in 1996; ticket is an optional extension since 2006. Although session-id is in the protocol you don't have to fully implement it -- a server can always return an empty session-id, and a client can always "forget" any session-id it receives. Ticket is mostly useful for servers with large numbers of clients -- like the many millions for google, yahoo, twitter, facebook -- which would need to save huge numbers of sessions and distribute/synchronize them across numerous machines in a server "farm" (solvable problems, but if you don't need to it's easier).
So to your specifics:

session-id is good as long as both endpoints choose to save it and have room. Usually this is minutes to maybe an hour at most, but it can be more if both endpoints support that. On implementations I've looked at, it's configurable per application. It fails gracefully -- if client discards the session for a server and sends ClientHello with empty, server just creates a new session and discards the old one if still saved; if client has (and requests) a session server has discarded, server forces a new one and client discards its old one.

When I've looked I've seen ticket provided (if client offers support) only on a few high-volume sites (and my OpenSSL testbench) but I don't claim to have made anything like a thorough survey and I haven't seen any published. As 5077 describes, if you do use ticket you effectively ignore session-id for that session. It could certainly make sense for server to allow ticket to be valid longer than it would have kept session-id in its (possibly limited and crowded) cache, but I don't have data.

Initial handshake is always unencrypted up to ChangeCipherSpec and Finished, except for specific elements. In particular for RSA keyexchange, client public-key encrypts the premaster secret to server. (For DH* and ECDH*, public-keys don't need to be encrypted and aren't but still produce a secret agreement.) And ticket if used is encrypted by server to itself. If you do use renegotiation, that entire handshake is (super)encrypted, even though it usually doesn't need to be, giving a (clumsy) way to get that functionality.


Which attacks are prevented by the different initial hash values for SHA-2 with truncated output? NIST specified SHA-2 hash functions with truncated output. Those hashes use different initialization values than SHA-256 or SHA-512. SHA-224 is based on SHA-256. SHA-384, SHA-512/224 and SHA-512/256 are all based on SHA-512.

Although I have seen loose comments on why truncated SHA-2 functions use different initial values, I haven't seen any strong reasoning. The only thing that I can formally find is a quote from RFC 3874: "A 224-bit One-way Hash Function: SHA-224", section "1.1. Usage Considerations:

  The use of
     a different initial value ensures that a truncated SHA-256 message
     digest value cannot be mistaken for a SHA-224 message digest value
     computed on the same data.

But that quote doesn't list any specific attacks nor is it part of a security review of SHA-2.

Can anybody explain which attacks are prevented by choosing different initial values for the SHA-2 variants?

I'm specifically looking for answers that indicate how the initial values help mitigate the attack. More importantly, I'm looking for authoritative answers, that is: answers that can point to a security evaluation or proof of SHA-2 on this subject.

The question's citation is likely the reason why it was chosen different initial starting values for SHA-2 variants of the same internal block size. It is a valid objective by itself that different hash functions yield independent results, linkable only knowing their common input. It is not necessary to have a specific attack in mind to make that conservative choice.

Otherwise stated: For an attacker knowing the SHA-1 of some secret, the best option to find the SHA-256 of that secret is to find the secret. Using different initial values makes it such that the same holds if the attacker knows the SHA-224 hash instead of the SHA-1 hash. That could be called (domain) separation of hash functions.

It is easy to construct artificial protocols where this precaution saves the day. For example: Alice draws a 80-byte random string $S$, reveals its SHA-224 (say, as a commitment or a Key Check Value), then uses $S$ as an HMAC key with SHA-256 as the underlying hash. HMAC will start by hashing $S$ with SHA-256, then use that as its internal key. With the different initialization values in SHA-224 and SHA-256, Alice is safe. Without, she's headed for disaster, as all but 32 bits of the HMAC key coincide with the leaked SHA-224.


what kind of custom header add to encrypted file to identify my encryption,consider safe and reliable.like pseudo format extension or file size I want to  add some  custom header to encrypted file to identify my encryption,consider safe and reliable.like pseudo format extension or file size.Is there any algorithm or tool to make it?

As indicated, the header format of your proprietary encryption is entirely up to you. Still, as I see this forgotten or done imperfectly a lot of times, I'll give some general hints in the right direction.

First of all, complexity is the enemy of security. If you make your header overly complex you may get into trouble. It could be possible to generate invalid packets, buffer overruns because of incorrect length fields or simply combination that do not make sense.

Furthermore you must be aware that attackers may be able to mess with your header format. This is mainly a problem for encryption formats that are or can be used for transport security. For transport security you should take care of man-in-the-middle attacks. So if an attacker can downgrade your security level through the header format then that's obviously a bad thing. You don't want to end up with all the configuration options for, e.g. IPSec. It makes no sense to allow (and code, and test!) AES-256 with MD5 configured together.

If you have lots of configuration options then those are likely to have a big influence on security if they haven't been established beforehand. So you must make sure you check your header format in advance. It's highly recommended to let your header format be included in any authentication tag calculation (MAC), and to make sure that that MAC verification itself isn't an issue. The simplest attack is simply to remove the MAC authentication tag entirely if your protocol supports it. This sort of attack actually happened on protocols like WS-Security (web services) due to broken implementations of both Glasfish and Apache/Tomcat where the signature was simply stripped off and the server accepted those messages without issue.

Probably the simplest header is a single identifier defining the version of the protocol. That version then defines a well defined suite of algorithms with parameters that make sense. So for instance byte version 01 would indicate that AES-GCM is used with a security level of 128 bits. The security level of 128 bits is then maintained for all other algorithms as well (e.g. key derivation with 256 bit hashes and RSA with 4K bit keys.

It may be useful to define an additional 8 byte constant value so you can identify the file type by looking at the content instead of the file extension (if applicable, e.g. for in place file encryption).

So there you are:

apply the KISS principle, don't allow overly flexible configuration;
make sure you are protected against attacks on the header and that buffer overruns are not possible (or at least warned against);
verify the validity of the header upon receival, checking as much as possible, and at least an authentication tag;
include a constant value for file identification when applicable.


Generating password from high entropy file Assuming

We want to generate a password of 32 bytes, using a keyfile as source but not using it directly but via an intermediate step;

So:

We have a file of 100MB file with high entropy
We ask the user to give 2 values, (A) one is the offset into the file, the 2nd (B) is chunk size

We then:

Open the file and skip to offset (A)
Read as many chunks of size (B) until end of file
Per chunk scrypt it into value (scrypt set to take ~1 sec), crc the out block to a integer value and add it to the 32 byte array (increment index for each chunk, reset to 0 when at 32)

If I'm correct it would take an attacker ~10 years to go through the whole keyspace with a brute force attack. Would this be correct or am I missing something here (probably) - as in for each byte (offset) there are 100MB/32 possible variations in size (there are some details that are important which I'm skipping over - but it's the general idea I'm thinking of)

J

If I'm correct it would take an attacker ~10 years to go through the whole keyspace with a brute force attack. Would this be correct or am I missing something here

No

First let's consider simple fact: The more power you have the shorter attack will take. There is no such thing as "it would take attacker 10 years". Also, 10 years is very, very short compared to proper key, which is very far from measurement in life-times.

Also, you seem to imply that fact that attacker will have to try multiple files will make it hard. Imagine that I have botnet with 40 000 machines. I can assign one machine for each of your files. So it will just take me as long as it took you to decrypt it (if not better). I can then try most common choices of A and B which would me take maybe day if i'm unlucky (considering that your decryption takes you minute, which is massive amount of time for password-based encryption).

While when you had used password with just 6 characters, I would have somewhat harder time recovering those.

If you assume that attacker knows your file, your whole process is basically useless. There simply isn't enough entropy in A, B and file selection. If you assume attacker doesn't know your file then all you do is still useless, because you would be just as secure in getting first 256-bytes of that file (since you assume that this file is high-entropy, if it isn't consistently high-entropy then you simply hash that file and end in same thing).

Also, one advantage of using passwords is that user himself choose how secure he is. If he uses 4-character password, it will be broken. If he uses 20-character password then there is good chance it will never be broken. With your scheme everyone who doesn't have 20TB worth of storage for keys is limited to 4 characters of security (and with 20TB you won't be much better).

TL;DR: Use established best practices. With your scheme you are arguably worse than with md5.

Also speaking of your scheme, it seems to come from world of "security by obscurity". There is no point in using crc-16 to shorten your key. Scrypt returns high-entropy mixed key, which you can simply cut. But your scheme doesn't spread entropy trough your returned key (which is terrible - you can know part of key with part of file). Also, you use scrypt to convert key to key, which is something pointless, since your key generation will take longer with longer file. So long in fact that user will get bored. Just imagine 60bytes file with A=0, B=1. It will take one minute to get key. You would be far better with just scrypting hash of whole file (you would still be able to configure scrypt time to something reasonable).


Verifying without knowing key? Say user Bob sends an encrypted message to a server. People can download the message from this server and later get the key directly from Bob.

Is it possible for the server to somehow verify that users are able to decrypt the message later on with Bob's key without letting the server be capable of decrypting the message itself?  So the server knows the message is being opened but itself can’t “see” the contents? Is it – at least theoretically – feasible to have an implementation which allows for this situation?

A solution from the top of my head:

Bob will end the server $(Enc(m), h(m))$ where $h$ is a collision resistant hash.
Now, Bob will interact with the server and provide a zero-knowledge proof that $m$ is the same one in $Enc(m)$ and $h(m)$.

We note that this verification is in NP (the certificate for the verification is the key used to encrypt $m$). Therefore, it is feasible to do the zero-knowledge proof part in polynomial time.


Why is padding the plaintext with a random string before encryption worse than OAEP / PKCS#7? I'm reading about OAEP / PKCS padding used for PGP to turn deterministic algorithms like RSA from deterministic encryption to probabilistic encryption (randomness in the resulting output). That way the same input encrypted with RSA should produce a different output each time.

However, the wikipedia page for probabilistic encryption addresses a seeming simple solution but doesn't give any details what is wrong with it:

  An intuitive approach to converting a deterministic encryption scheme into a probabilistic one is to simply pad the plaintext with a random string before encrypting with the deterministic algorithm. Conversely, decryption involves applying a deterministic algorithm and ignoring the random padding. However, early schemes which applied this naive approach were broken due to limitations in some deterministic encryption schemes. Techniques such as Optimal Asymmetric Encryption Padding (OAEP) integrate random padding in a manner that is secure using any trapdoor permutation.

Can someone explain (to a beginner) what is insecure about random padding being added?

In addition, for PGP encryption using RSA, my understanding is that a random nounce / AES key is generated and encrypted using RSA. Then that AES key is actually used to encrypt the source text.

So, if the whole AES key is random to begin with (and required to know anything about the encrypted text) - what exactly is OAEP adding?

The padding used for RSA is not the PKCS #5/#7 padding (as you seem to suggest in your own answer), but the Wikipedia entry seems to refer to PKCS #1 v1.5 (RFC2313)) which uses a padding

00 || BT || PS || 00 || D

where for RSA encryption we start with a 0x00-byte (to guarantee that the resulting number is below the modulus), then use BT (Block Type) equal to 0x02, the padding string (PS) is at least 8 long and consists of random non-zero bytes, the single 0x00 is added followed by the actual data being encrypted (D), and so that the total length equals the effective length in bytes of the modulus.

The padding can then be uniquely removed because the start of the RSA-decrypted block should follow this pattern that we can check, and we strip random bytes until we meet the first 00, after which we have the data.

The problem lies in implementations that check this padding and that somehow leak (e.g. by the different possible error responses, or time used for checking etc.) how exactly the padding removal failed (no start 00, no 02 byte, padding too short, data unexpected length..) and attacks were developed based on that (see Bleichenbacher oracle etc.). So the padding does work, but it is "ad hoc" (it has no proof of security) and it's too easy to do the checking in a wrong way. Hence OAEP, which has more of a theoretical basis.


Protocol composition I have been trying to wrap my head around different definitions of protocol security (stand alone, sequential composition, parallel composition, universal composition) and how the proofs of any of these cases are obtained. However, at current state I find it quite complicated. Can you recommend any good lecture materials or maybe survey articles that would help to get into this topic?

Protocols for Authentication and Key Establishment [1] By Colin Boyd is considered very good book. That has plethora of examples, proofs etc. in very understandable language and format.

Another book is Modern Cryptography Theory And Practice [2] by Wenbo Mao. Few chapters have very good introduction to designing protocols in attack-fix cycles.

and few more

Boyd, Colin, and Anish Mathuria. Protocols for authentication
and key establishment. Springer, (2003).
Wenbo, Mao. "Modern cryptography: theory and practice." Publisher: Prentice Hall PTR,
Copyright: Hewlett Packard (2004).
Cremers, Cas, and Sjouke Mauw. Operational semantics and verification of security protocols Berlin: Springer, 2012. This is an excellent single book that covers all the aspects needed in great detail and rigor.
Bella, Giampaolo. Formal correctness of security protocols. Heidelberg: Springer, 2007.


Significance of repetition in XOR cipher text I'm attempting to recover plain-text ($P_1, P_2$) from two uneven cipher-text strings ($C_1, C_2$) that I suspect used the same key ($K$).

When I XOR $C_1$ and $C_2$ together to obtain ($P_1 + P_2$), there is repetition of a string of characters several times within the XOR string e.g:

.81afg.81afg.81afg.81afg.81afg.81afggyuwokjjkdjkkljlklkaiiuwqnnmc,mkhjaioqn

What is the significance of the repetition? Does it mean that a 6 character key was used and repeated across the same characters within $P_1$ and $P_2$?

What is the significance of the repetition? Does it mean that a 6 character key was used and repeated across the same characters within $P_1$ and $P_2$?

I'm assuming your assumption about this being an xor cipher with the pad used twice for two ciphertexts.

It does not mean a 6 character key was used. A one time pad used twice could result in this behavior.

It means that the first 6 characters of the first plaintext xored with the first 6 characters of the second plaintext results in .81afg. Furthermore, the 2nd 6 characters of the first plaintext xored with the 2nd 6 characters of the second plaintext results in .81afg. We also know where the bits in the two plaintexts are equal and where they are different, but we don't know what the bits are.

Now that doesn't help much, does it. If I had to guess, though, I would guess that there is a 6 character sequence at the beginning of each plaintext that repeats 6 times. If this assumption is correct, then we know that the sequence changes between the encryptions (otherwise we'd get all 0's). Remember though that this is just a guess.


Distinguishing x25519 public keys from random? I recently read a piece of protocol that avoided sending ephemeral x25519 keys in the clear as an effort to foil deep-packet inspection.

I understand that x25519 public keys are effectively 255 bits, which must be serialized as 256 bits, leaving one unused bit that libraries typically fix as 0. For the purposes of this question, I'd like to leave this out and focus on the 255 used bits.

Alice generates a random private key K, and 255-bit public key K'. She generates R, a 255-bit random string. She flips a fair coin, and if heads, she sends a message M = K'. Otherwise, she sends M = R.

Eve receives this message and does not know K. She must guess whether M = K'. Can she do this with better than the 50% success rate she'd get by guessing? (In other words, can she distinguish the significant bits of a x25519 public key from random?)

edit: in response to a question, Eve has knowledge of the curve parameters.

A valid point of an elliptic curve in Weierstrass form satisfies the equation
$$
y^2 = x^3 + ax + b\,.
$$
We can rewrite this as $y = \pm \sqrt{x^3 + ax + b}$, which has either 2 solutions when $x^3 + ax + b$ is a square, 1 solution when $x^3 + ax + b = 0$, or 0 solutions when $x^3 + ax + b$ is not a square.

In X25519, we only see the $x$ coordinate, but we can still make use of the above. The curve equation is
$$
y^2 = x^3 + 486662x^2 + x \bmod 2^{255}-19\,,
$$
from which we have that given a valid public key $x$, $x^3 + 486662x^2 + x$ must have a square root modulo $2^{255}-19$. On the other hand, a random string will be a square only around $1/2$ of the time. By inspecting $n$ candidate public keys, we can improve our certainty to $1 - 1/2^n$.


Norms in differential privacy I know that perturbation should be proportional to the $\text{L}_1$-sensitivity of the function if someone wants ($\epsilon,0$)-differential privacy, and proportional to the $\text{L}_2$-sensitivity of the function if someone wants ($\epsilon, \delta$)-differential privacy for $\delta > 0$.

But why is that? Can anybody describe the intuition behind the use of these two norms? Or maybe share some resources?

I don't think there is a direct between the type of norm and whether $\delta=0$. For example, this crypto.SE answer mentions a mechanism that is pure $\varepsilon$-DP and scales with $L_2$-sensitivity. Conversely, some $(\varepsilon,\delta)$-DP mechanisms scale with $L_1$-sensitivity, like the truncated geometric distribution from this paper.
However, the most commonly used noise mechanisms used in DP are Laplace noise and Gaussian noise, which respectively scale with $L_1$ and $L_2$ sensitivity; the first one is pure $\varepsilon$-DP while the latter only provides $(\varepsilon,\delta)$-DP. You can find a "visual" representation of why that's the case by looking at the density function of a multi-dimensional Gaussian (top) vs. Laplace (bottom):

This picture is taken from this blog post of mine about Gaussian noise.


What is largest prime factor in Diffie-Hellman? I was reading the paper of A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms by TAHER ELGAMAL to better understand ElGamal public-key scheme, and he stated that for any cryptosystem based on discrete logarithm problem, the prime $p$ should be chosen such that $p-1$ has at least one large prime factor.

My question is the following: how to determine if the largest prime factor of $p-1$ is in fact large?

How to determine if the largest prime factor of $p-1$ is in fact large?

Most often, it is not determined from $p$ that $p-1$ has a large prime factor. Rather, a large prime factor $q$ is chosen, then it is chosen a prime $p$ of the form $p=2\,q\,r+1$ for some $r\ge1$, which insures that $p-1$ has large prime factor $q$.

Sometime, we want $r=1$, in which case $p$ is a safe prime and $q$ the matching Sophie Germain prime. See last paragraph for how these are searched.
For some other applications, we want $r$ large so that $p$ is much larger than $q$ (e.g. $p$ 3072-bit with $q$ 256-bit). This the Schnorr group case. For the search of $r$ making $p$ prime, when that does not hold, we typically add a small value to $r$; perhaps $1$, or a small random value in order to make $p$ more randomly seeded.Standard generation procedures for Schnorr groups are in FIPS 186-4 appendix A.

More rarely, it is checked after the generation of $p$ that $p-1$ has a large prime factor.

For a safe prime, that boils down to checking that $(p-1)/2$ is prime.
Otherwise, we could compute the small prime factors of $(p-1)/2$, multiply them (with multiplicity) to get $r$, then check if $q=(p-1)/(2\,r)$ is prime. If it does, and is suitably large, that validates $p$ (but we could fail to pull enough factors). This would only be useful for exploration or forensics: prime $q$ is typically needed to use $p$, therefore such $q$ is usually moved along $p$.

Quick search of safe primes (larger than $5$ and $7$)

Typically, we also want a certain generator $g$ (often $2$ or $3$) known to be of order $q=(p-1)/2$ (maximal prime order) or order $2\,q$ (maximal order, which is not possible for $g=3$ ). The search can be as follows:

for each candidate $q$ (necessarily: with $q\bmod6=5$; and further with $q\bmod12=11$ for $g=2$ of order $q$, or with $q\bmod12=5$ for $g=2$ of order $2\,q$ )

compute $p=2\,q+1$
compute $t=g^q\bmod p$
if $t=1$ (for $g$ of order $q$) or if $t=p-1$ (for $g$ of order $2\,q$)

if $q$ is prime

if $p$ is prime

output $p$ and stop.

The test of $t$ is a Fermat pseudoprime test. It quickly filters out most candidates $p$ that are not prime, and all primes $p$ with $g$ not of the desired order. If for some reason we do not care for a generator, it still pays to compute $t$ with $g=2$ and accept both $t=1$ or $t=p-1$.

The search can be made faster by selecting thru sieving only candidates $q$ with neither $q$ nor $2\,q+1$ divisible by a small prime.


randomly generated key reused with XOR If I have a long randomly generated key (k), XORed with a message (m), but since the message is longer than the key, there is a chance of reusing the keystream with the same message, but the key is used only onetime for every encryption process. In other words, every time I have to encrypt a message, I randomly generate a bit key with variable length.
Can we consider this technique is secure against any attack even though the keystream is been reused with the same message despite the fact that I have to save the key for every message I encrypt?

Apart from the obvious security vulnerability from using a simple XOR operation to convert between plaintext and ciphertext you also run into the massive security-flaw of each identical plaintext generates identical ciphertext.

In any given message, if a constant cipher operation is used along with a constant key, the resultant ciphertext will be same for every plaintext irrespective of the position of the plaintext within the message. This property causes patterns in the original plaintext to be revealed in the ciphertext.

Take for instance AES-ECB where even though a strong block cipher (AES) is used, a cipher operation that generates identical ciphertext for identical plaintext exposes the "pattern" of the message.

For a visual demonstration of this problem consider these images:

(Image courtesy of Wikipedia)
The first image shows the original message (a bitmap of the linux logo). The second image shows a encrypted version the same logo using AES-ECB. Notice how the pengiun can still be distinguished even after encryption.

This is due to the fact that every white sector in the image is passed through the cipher operation and generates an identical ciphertext causing the areas with differing colour to produce differing ciphertext in a manner that exposes the patterns of the original image.

To summarize, not only are you using an extremely insecure cipher operation of XOR (Information of why it is insecure is cluttered all over the web), using a cipher that generates ciphertext that is identical when the plaintext is identical is a security flaw in itself. Given that you are reusing the keystream for messages longer than the key, you definitely fall for both these vulnerabilities.


How to encrypt numeric data on a ticket I have a customer with an existing ticketing system that generates tickets for events like theaters, movies, football and so on.

The information in each ticket is encoded in a 16 decimal digit numeric string. The information contains fixed positions for event date, event identifier, seat row, seat number and so on.
This system has a numeric barcode on each ticket with room for 20 decimal digits. (https://en.wikipedia.org/wiki/Interleaved_2_of_5)

The main problem is that it is too easy for adversaries to generate false tickets with valid barcodes.

My customer now wants to encrypt the information in the barcode to make it more difficult to generate false tickets.

The requirements are as follows:

The plaintext is a 16 decimal digit (0-9) string.
The ciphertext is a 20 decimal digit (0-9) string.
Consecutive ticket numbers might differ only in a single digit position in the cleartext, the ciphertext for consecutive tickets must still be completely different.
It should be impossible to calculate the encryption key even if you have access to many valid tickets.
The encryption key is the same for all tickets for a certain event.
It must be difficult for an adversary to generate a valid ticket number, especially for a specific event.
Barcode readers used for validating tickets should work completely offline - it is not possible to have a complete database of valid ticket numbers available to the barcode readers.
Note that the 20-digit encrypted barcode after decryption must contain the full 16-digit plaintext. This means that we only have room for a 4-digit hash.

What kind of encryption and authentication should we use in this case? As I see it, the main problem is that the space in the barcode is very limited, so we can not use a real HMAC.

Any suggestions?

Given that we can add only 4 digits (13.3 bits) of redundancy, there is no way to use asymmetric cryptography. We'll have to use a secret key in the verification terminals.

This is an application for Format Preserving Encryption. It can act like a block cipher, except we can decide the block width, and deal with decimal rather than binary or hexadecimal digits. Methods for FPE are given in NIST SP 800-38G. The previous link leads to references with other methods.

Take the 16-digit plaintext, append four zeroes, yielding 20 digits. Encipher that using FPE, yielding 20 digits, put that on the ticket.

On reading a ticket, check that it is 20 digits, decipher per FPE (yielding 20 digits), and consider the result valid when it ends with four zeroes; remove these.


How many hex digits do I need to compare when manually checking hash functions? I sometimes run sha256sum on large files after transferring them from one place to another, and will just skim the hash output to verify it's correct. But, I usually just look at the first/last 5 or 6 hex digits and call it good enough.

I know that the chances of collision are something like 1 / 2^64, but what are the chances of a "near collision"? E.g. only one or two hex digits are different.

As a related topic,
If you have a binary sequence and just change one bit, you get a completely different hash, correct? So is it possible for random errors to result in nearly identical hashes? I'm aware that MD5 is 'cracked' such that a malicious agent could append whatever necessary data to a file to make it have the same hash output- but is this within any reasonable realm of possibility to have happen stochastically?

EDIT: This topic has spawned some discussion below that was just as (if not more!) informative than the scope of my original question. With that said- I am referring only to using hash functions as a file integrity check, not as protection against attacks.

How many hex digits do I need to compare when manually checking hash
  functions?

If you actually want the full security guarantees of the hash function to apply: all of them.

  I usually just look at the first/last 5 or 6 hex digits and call it
  good enough.

This effectively reduces the security of the hash function to that of one that only outputs 10-12 hex digits, a.k.a. 40-48 bit, for which we can easily find collisions in about $2^{24}$ evaluations which is easily doable.

  what are the chances of a "near collision"? E.g. only one or two hex
  digits are different.

As discussed in this answer the probability for at most $t$ bits difference between two hashes with $n$ bit output-length is $$p_t=\sum^t_{k=0}{n\choose k}2^{-n}$$ which means you need about $\sqrt{1/p_t}$ evaluations to come up with a desired near-collision. Strategies to finding these values can be found in this answer (including low-memory approaches).


Recommendation for lightweight algorithm for partial message encryption I have designed a specific client and server program, which sends a file  from client to server in 32k chunks. I want to encrypt only part of the data. More specifically: in each 32k chunk passing from client to server I want to encrypt only 500 bytes. This, in a non-continuous way (meaning: partial encryptionhere and there in the chunk of 32k, totally forming 500 bytesof encrypted data within the 32k block). Here client is a constrained sensor and server is an Arduino board used for Internet of Things concept, to save of energy of the constrained device(client) i want to encrypt only parts of data.

Are there any lightweight(here refers to C.P.U consumption) cryptographic algorithms or methods which offer  the option to set an “offset” and a parameter defining how much partial data we want to encrypt?

For example encrypt (bufptr, random_num, ENCRYPT_LENGTH); where bufptr is a 32k chunk with information, random_num is the random number smaller than the bufptr pointing to the bufptr, ENCRYPT_LENGTH is the length we want to encrypt (like 20 bytes from the number pointed by the random_num).

It's trivial to code your own wrapper function if you really want to use such API. Here is a Python-inspired pseudo code:

def mywrapper(data, offset, encspecs):
    subdata = data[0:offset]
    ciphertext = whatever_enc_function(subdata, encspecs)
    return ciphertext

encspecs = ...
plaintext = "...etc"
ciphertxt = mywrapper(plaintext, offset, encspecs)
cipher_plain_mixed = ciphertxt + plaintext[offset:]

But either way, it's not an algorithmic/methodology problem as much as it is an implementation.

Side note: I sense that you are about to allow for replay attacks, or other similar ones. Make sure to include a unique initialization vector (e.g. a simple counter or timestamp) that is always different, so that you never (extremely rarely) get same cipher again even when the content plaintext is repeated. This prevents an attacker from fraudulently re-sending a previously captured block of encrypted data.


Is it safe to use the same password/secret for both VeraCrypt volume and its HMAC? I am trying to script the integrity check of a VeraCrypt volume.
#! /bin/sh

red=$'\e[1;31m'
end=$'\e[0m'

set -e

printf "Please enter password: "

read -s p

if [ -f "/Volumes/Samsung BAR/bar.hmac" ]; then
  printf "\n%s" "Checking integrity..."
  if [ "$(openssl dgst -sha512 -hmac "$p" "/Volumes/Samsung BAR/bar")" != "$(<"/Volumes/Samsung BAR/bar.hmac")" ]; then
    printf "\n%s" "${red}Check failed${end}"
    exit 1
  fi
fi

printf "\n%s\n" "Unlocking VeraCrypt volume..."

veracrypt --text --non-interactive --mount --pim 0 --keyfiles "" --protect-hidden no --password "$p" "/Volumes/Samsung BAR/bar" /Volumes/Backup

declare -a files=(
  "/Users/sunknudsen/.gnupg"
  "/Users/sunknudsen/.ssh"
  "/Users/sunknudsen/Library/Keychains"
)

for file in "${files[@]}"; do
  rsync -axRS --delete "$file" /Volumes/Backup
done

open /Volumes/Backup

printf "${red}Inspect backup and press enter${end}"

read -r answer

veracrypt --text --dismount "/Volumes/Samsung BAR/bar"

echo "Saving HMAC..."

openssl dgst -sha512 -hmac "$p" "/Volumes/Samsung BAR/bar" > "/Volumes/Samsung BAR/bar.hmac"

echo "Done"

Security warning: Using read -s p is vulnerable to process listing leaks so I need to find another way to feed the password to both openssl and veracrypt.

Assuming your password is secure, yes it is (and I've seen your YouTube channel so I guess that's a non-issue). If you use the same key in both, an attacker would still have to find your key. Since your data this encrypted this requires breaking either the encryption or the HMAC'd hash - even if the hash is broken, they may find a collision but your key would be significantly harder to obtain, since collisions usually don't involve finding the original data.
The point of HMAC is to pair the data with the hash. Someone may tamper with the data, but without the key they can't make the hash collide with the new data. You can use one or multiple keys, it really doesn't matter.
Also, don't forget to store 2 separate hashes. That way, if one has a collision attack developed later on, you can still verify the authenticity using the other. SHA-512 and BLAKE2b? (C'mon, don't tell me forked their official implementation for nothing)
Just kidding, but really... Store the hash with 2 separate algorithms.


What is the purpose of multiple key addition layers in AES? I understand the purpose of the SubBytes layer (confusion) and the ShiftRows and MixColumns layers (diffusion).

But I don't see the purpose of having more than one key addition layer. What I've been able to find is that it can mitigate side channel attacks if the AES implementation leaks information, but I don't see the connection there.

Suppose you remove the key addition layer. What happens then?

(Mouse over to see the answer. Try figuring out yourself first!)

   Denote AES without the key addition layer by $\operatorname{f}$. Suppose an adversary has $\operatorname{f}(x)$. They can recover $x$ by applying $\operatorname{f}^{-1}(x)$. If there is no secret information (the key), then anyone can perform the permutation/inverse permutation at will. You cannot have confidentiality without a secret decryption key.

Edit in response to modified question

If the key is only applied once, then given a ciphertext an adversary can apply the inverse permutation on the ciphertext until they end up with $m' \oplus k$. This allows them to recover $k$ via exclusive-or with $m'$, where $m'$ is the result of $f'(x)$ and $f'$ is the first steps of AES up to the key addition layer.


Format Preserving Encryption for 32 or 64 bit plaintext values I am looking for a Format Preserving Encryption implementation to apply to either a 32-bit or a 64-bit integer.  It looks like AES/FFX mode is just what I need in terms of established security properties.  However, it looks like it is patented, and it seems like there might be something equally solid in the public domain for the special case of 32 or 64 bit data, ideally with C source code.  I have seen SkipJack or 3DES for the 64-bit case, but I would prefer longer key sizes, as these will be statically configured.

The application is to compartmentalize/anonymize information in a database.  I have different kinds of information about users that is not terribly privacy invasive as long as it is kept separate from other kinds of information that is also not invasive on it's own.  However, there may be rare cases when I need to connect this data together.  So, I was thinking each database would identify users with its own ID, and the key to connect them could be stored separately.  The actual application is a little more complicated, but that's the general idea.

I'm not aware of any implementations, but I'm also not aware of any patents on this algorithm.

Furthermore, that algorithm can quite directly be made tweakable,

as that paper describes on pages 10-13.


What is the purpose of adding secondary error to calculated key in BCNS and NewHope protocols The answer to this question might be trivial or very short, but I would like to ask it anyway. In both BCNS and NewHope Ring-LWE key-exchange protocol one party adds a secondary error to their calculated key. What is the reason? Is it just to increase entropy? Or is there another a reason behind it?

BCNS protocol (page 8): notice that $e''$

NewHope protocol (page 5): notice $e''$

If $e''$ isn't there, then $v=bs'$ in both protocols, which means it would be easy to recover $s'$ given $v$ and $b$. Since $b$ is sent in the clear over the channel, and a (randomized) function of $v$ appears in the clear as $c$ (or $r$), without using $e''$ to hide $s'$, information about $s'$ would likely be leaked both to Alice and to any eavesdropper of the channel. Even if it wouldn't immediately leak all of $s'$, any leakage is clearly bad.

Somewhat related to this is the history of lattice signatures, which initially leaked "just a little bit" about the secret key, after which full breaks of these schemes were found. These schemes were only truly fixed once a way was found to make the output distribution completely independent of the secret key, so that nothing is leaked. In this case $e''$ is used to make sure that $v = bs' + e''$ is indistinguishable from random, i.e. the distribution of $v$ is independent of $s'$, assuming R-LWE is hard. See also the security proof in the BCNS paper, where Game 1 and Game 2 are assumed to be indistinguishable under the R-LWE assumption.


How many parties are needed to compute multiplication with BGW? Let's say we have 3 parties and each one of them has a different secret number. Every party wants to learn the product of all the 3 numbers without learning about the other inputs.

With the BGW protocol: Can we do this with 3 parties, or do we need 5 parties to do this? I am confused because BGW states that we need $2t+1$ parties to reconstruct the solution, which would be 5.

The BGW protocol has a semi-honest and a malicious version. For semi-honest, a simple honest majority is enough. In that case, 3 parties can run the protocol, with security against one (semi-honest) corrupted party. For malicious adversaries, BGW requires $t < n/3$ meaning that with one corrupted party, you need at least 4 parties; with up to two corrupted parties, you need at least 7 parties.


Is Checksum to file back decoding possible? So, I was having this weird thought. If the checksums(MD5 or SHA...) are unique to any file and are modified if any part of the file is edited, why cant the checksums be decoded back to get the original file? That is if I want to send a large(say 700MB) video, instead I could send just the hash and the file be decoded locally in my friend's computer. I know the thought is stupid, but is it possible by any chance? Or am I missing some thing here? And forgive me if I'm wrong, I ain't a professional.

If the checksums (MD5 or SHA...)

First things first: there is a BIG difference between a checksum (aka “cyclic redundancy checks” like CRC32) and a hash (aka “cryptographically secure hash functions” like MD5 and the SHA families).

The biggest difference between checksums and hashes is that checksums are neither build, nor meant to be cryptographically secure. (Checksums are mainly used for error detection; eg after file transfers.) To get a better understanding of the different categorisations, you might want to take a look at Wikipedia: List of hash functions.

Anyway, let’s get to the core of your question…

  Is Checksum to file back decoding possible?

No, that’s not possible. Neither a checksum, nor a cryptographically secure hash enables you to rebuild the data it was created from. The reason is simple: both hashes as well as checksums are one-way functions. They “compress” the information down to a level that makes it infeasable to revert them.

In fact, you could almost compare them to lossy compression algorithms which compress information beyond the point of recoverability, but in a way that even a single bit change of the original file will result in a completely changed hash or checksum.

Especially when talking about cryptograhically secure hash functions like SHA2, SHA3, et al (MD5 is regarded not to be so secure anymore in all cases), you should note that an ideal hash function has three main properties:

It is extremely easy to calculate a hash for any given data.
It is extremely computationally difficult to calculate the data which was used to create a specific hash.
It is extremely unlikely that two slightly different messages will have the same hash.

Here, “extremely difficult” practically tends to boil down a situation where “brute-force” is your only chance. So, the receiver of your 700 MB video file would need to create several thousands of versions of 700 MB files using random data, then hash that data and only if the hash fits your hash, the receiver would be sure to have a copy of the file you hashed.

Simpler said:

Creating a checksum or hash is very much different from a regular data-compression algorithm like ZIP/deflate. If you test things yourself, you’ll quickly notice that even the best file-compression program will not be able to shrink your 700 MB video file down to a few hundred bytes… for a good reason. Those programs need enough data to reconstruct the original file. A hash or checksum doesn’t offer any such “decompression” functionality as it isn’t meant to do that in the first place (see emphasised point of above property list).

Both hashes and checksums produce a (let’s just call it) “unique summary describing the data”, but they do not hold, contain, or are able to reproduce the original data.


Active S-boxes for AES with 8x8 MDS matrix One way to enhance the security of AES is by increasing the number of active S-boxes. Larger MDS matrices are used to increase the number of active S-boxes. Using a $4\times4$ MDS matrix results in 25 active S-boxes after 4 rounds.
How many S-boxes would be active after 4 rounds using an $8\times8$ MDS matrix?

It seems that using an 8x8 MDS will have 27 Active Sboxes after 4 Rounds(There may exist a trail shorter than 27). The image below shows the counting of active Sboxes.

The Active and non-Active byte is shown as 1 and 0 respectively.
The 8 bytes of state which become input to the 8x8 MDS matrix are
colored in similar color (pink or blue).
The shift rows step shows new byte position in pink and white color.
The calculation is done under the assumption that 8x8 MDS matrix has
optimal branch number of 9 i.e change in one byte will change all
the 8 output bytes.
If 8x8 Matrix similar to Camellia is used which
has branch number of 5, then count of active Sbox may be reduced.


One-Time Pad Distribution of Keys Between Two Parties Consider the One-Time Pad (OTP). Suppose two parties, A and B, generate a completely random secret key in a real-life meeting, and they keep this secret. Now A wants to send some message to B using the OTP. The point is that in the OTP we can use any key only once. So we have to come up with a system to share a newly chosen key in a secret way.

Why cannot A just concatenate a new randomly generated secret key (needed for the next communication between the two parties using the OTP) to this message?

For instance, A could concatenate this new key at the beginning of the message.
(Supposing they have agreed upon a fixed key-length beforehand, so that B is able to tell which is the new key and what was the "actual" message.) In this way A and B would agree on a new secret key which they can then use for their next communication.

Probably this is insecure, but I do not immediately see why…

Let's say Alice and Bob have $c$ bits of pre-shared secret key material.  Alice generates $a$ bits of new key material, concatenates it to a message $M$ that is $b$ bits long, and uses $a+b$ bits of their pre-shared key material to encrypt "message||new-key".  She sends this secure message to Bob, who decrypts it with the shared key.  Now they both have $a$ bits of new shared key-material, but in order to securely send those $a$ bits and the $b$ bit message $M$ they had to burn through $a+b$ bits of the previous key material.  The total key material they now have to encrypt future messages is:

$c-$ (Amount spent to send "message||new-key") + $a$.

The term (Amount spent to send "message||new-key") = $a+b$, so the amount they have left is:

$c-(a+b)+a$,

$= c-a-b+a$,

$= c-b$.

So they are no better off now than if Alice had simply send the $b$ bit message $M$ alone without an appended new key.


Why does PHP crypt give this unexpected result So I have this PHP code,it is meant to encrypt a users password...
Three problems/questions:

My 'salt' CHANGES ITS NAME
I get the same result
Is this actually how the result is meant to be?

PHP CODE

<?php
$password=$_POST['password'];
?>

<?php
if (CRYPT_BLOWFISH == 1)
{
echo "Blowfish: " . crypt("$password", '$2a$09$anexamplestringforsalt$');
}
?>

RESULT:

Blowfish: $2a$09$anexamplestringforsaleU79j3Xck4QHAVNZ.exkIn8ZZrZnIrHq

As you can see, my salt goes from $anexamplestringforsalt$ to $anexamplestringforsaleU. (Or is that supposed to happen?) Also, that is the same result I get even after changing the password.

Please help.

The algorithm called "bcrypt" (which is not the same as blowfish) accepts a salt up to 128 bits long. The bits are encoded similar to Base64, just using a different map from bits to characters. Thus the maximum length your encoded salt can be is 22 characters.

Your salt looks like anexamplestringforsalt. That's 22 characters long. Note that 128 bits divided by 6 (or $\log_2 64$) bits per character is actually 21 characters with 2 bits remaining.

Try replacing the final 't' with different characters. You will see that the result will always replace the 22nd character with one of . O e or u. The 23rd character and onward of the (actual 128-bit) salt are truncated, having no impact on the result.

The PHP crypt function, atleast for bcrypt version 2a, uses only the first 128 bits. Additional bits are silently ignored. When I look at the relevant PHP source code it seems like this is deliberate. (Whether this was originally intended or if this was added to keep backwards compatibility, I don't know.)

The "U" in anexamplestringforsaleU is actually part of the hash, not the salt.

The reason why the final character only may take on one of four values is because that is the number of values the final 2 salt bits can take on. The reason why it's limited to . O e or u specifically is because the final character of the radix-64 string encodes those last two salt bits as the most significant two bits of the radix-64-digit. The low four bits are all forced to zero. . O e and u correspond to radix-64-digit numbers 0, 16, 32, and 48 respectively.

The alphabet is reproduced below based on this source. (I split into four segments for sake of clarity.)

./ABCDEFGHIJKLMN
OPQRSTUVWXYZabcd
efghijklmnopqrst
uvwxyz0123456789

Notes:

Use the Password Hashing API instead of crypt. It's already installed by default, it has reasonable defaults, supports bcrypt and argon2, and can generate salts automatically. The crypt function is much more difficult to use correctly.

Look into using Argon2. It uses relatively large amounts of RAM as a means of making password cracking more difficult.

The correct verb to use to describe password stretching/verification algorithms is usually "hash" not "encrypt". Password hashing is a one-way process (only brute force can "reverse" it). Encryption uses a secret key and is reversible. crypt was deceptively named.

Blowfish and bcrypt are not the same algorithm. Bcrypt is merely based on Blowfish.


What is a 76-step SHA1 collision? From Twitter:

  Marc Stevens released a new 76-step (out of 80) SHA-1 collision, and SIMD libdetectcoll https://marc-stevens.nl/research/

What is a 76-step collision, and how does it differ from a "regular" collision? Is it related to whatever a "freestart" collision is?

Analysis of a primitive often times is conducted on a reduced strength variant of the actual algorithm. This makes it easier to find the weak points of the design, which can become obscured after many iterations.

Assuming a "regular" collision means a collision over the entire 80 rounds, then a 76-step collision finds a collision after 76 rounds.

The paper for the result in question does mention that it is for a free-start collision. As for what this means, there is a Q/A here that does a goob job of explaining. Basically, it means that the attacker is allowed to select the initialization vector.


How to require two PRIVATE keyholders to decrypt a document? Consider 3 entities A,B and C. I want A to be able to encrypt a document that can be decrypted only when keys of both B and C are combined. This question talks about a similar problem, but it uses AES.

In my usecase, I don't want the keys to be shared across the entities. There is one solution that was coming to my mind:
A encrypts the document (with RSA) first using public key of B and then public key of C. Then the document is decrypted using private key of C and then private key of B.

Is this approach feasible? Is there a better way?

Note: I tried doing this but got this error when I was doing encryption for the 2nd time: Data must not be longer than 117 bytes.

Yes, you can use a symmetric secret sharing scheme, where the parts required for secret sharing are encrypted with the keys of B and C. Once B and C decrypt the parts they can combine their parts to create a symmetric data key, which is the key that is used to encrypt the document.

The very simplest way of sharing a key between two parties is to create a random data key and encrypt the document. Then create a random byte array with the same size as the data key, call it the key part of B. XOR this key part with the data key; the result is key part of C.

Now simply encrypt the key parts of the respective parties with their public keys. Now they can only access it using their private keys. For sharing, they can decrypt their part and send their key part to the other party, if required encrypted with the other parties public key. That way the final party that gets the ciphertext and both key parts encrypted with their public key. They can decrypt, combine the key parts using XOR, giving the data key. Finally they can decipher the ciphertext.

This will also solve the issue with the size of the plaintext message. RSA is limited to a certain amount of data, so in case of a 1024 bit key, you only get 117 bytes of plaintext message. However, if you use AES/GCM and RSA/OAEP in the secret sharing scheme above, then you can encrypt a message of any size with the symmetric cipher.

Note that 1024 keys are not considered all that secure anymore; you should use a key size of 3072 bits or higher. PKCS#1 v1.5 padding, that you are using, is also considered less secure nowadays due to the Bleichenbacher attacks on it.


What is the default behaviour, if no ciphers are enabled Lets assume for example, that a server is configured to use TLS 1.0 and there are no ciphers enabled for it.
What will be the default behaviour if a client connects to it?
Will the server use any null ciphers by default to complete the TLS handshake?

Will server use any null ciphers by default to complete the ssl
  handshake.

No. The TLS v1.0 specification explicitely states that the TLS_NULL_WITH_NULL_NULL cipher suite must not be negotiated. However, using a cipher suite that only offers authentication but no encryption is valid (and done in e.g. Windows Update). An example for such a suite is TLS_RSA_WITH_NULL_SHA.

To quote appendix A.5 of RFC2246:

  TLS_NULL_WITH_NULL_NULL is specified and is the initial state of a
  TLS connection during the first handshake on that channel, but must
  not be negotiated, as it provides no more protection than an
  unsecured connection.

$\space$

  Lets for example, a server is configured to use TLS1.0 and there is no
  ciphers enabled for it, what will be the default behaviour if a client
  connects to it.

It depends, either the server implementation will override your configuration and use the default list of accepted cipher suites, or it will refuse all incoming TLS connections because no client can offer an accepted cipher suite to the server (because it doesn't accept any).


How is padding oracle attack mitigated by encrypt-then-MAC? Let us suppose Alice sends a message to Bob.

As far as I know, the most popular scheme of MAC-then-encrypt is as follows: Alice computes the HMAC of the plaintext using her private key, and then encrypts plaintext+MAC by random one-time symmetric key, which is, in turn, encrypted by Bob's public key.

Padding oracle attack allows Eve to reconstruct the plaintext+MAC by sending modified versions of Alice's message to Bob and observing whether the modified version will trigger padding error or MAC verification error (when Bob will try to decrypt the encrypted message by symmetric key).

It is said (e.g. Should we MAC-then-encrypt or encrypt-then-MAC?) that switching to encrypt-then-MAC should mitigate the possibility of attack.
In that scenario, Alice first encrypts plaintext by random one-time symmetric key, which is, in turn, encrypted by Bob's public key, and sends both encrypted message and its HMAC computed using her private key.

I don't see how that prevents padding oracle attack, as long as Bob accepts messages from everyone (including Eve). Eve still could modify Alice's encrypted message, compute HMAC using Eve's private key, and send it to Bob.

Does encrypt-then-HMAC actually prevent padding oracle attack in this scenario?

The biggest issue with padding oracle attacks are when the padding is not very carefully implemented (for example if using EtM you must calculate the MAC over everything - including the padding). To pre-empt references to the classic Belare-Namprempre paper, be wary - their results do not apply to modern primitives, since nowadays we prove security differently. See instead the relevant Namprempre-Rogaway-Shrimpton paper from Eurocrypt 2014 (discussed here).

Padding oracle attacks are (supposed) to be mitigated by only presenting a single error. This is pretty well standard now (in that a sensible scheme will just say 'invalid' rather than 'padding wrong' etc), but timing errors exist that allow you to differentiate padding errors from other errors.

The idea is the in Encrypt-then-HMAC, you are always calculating the MAC over the entire message. So, let Bob receive a message, which he will parse as $(C||T)$. He will calculate $HMAC(C)=^?=T$. He can do this without caring how $C$ was put together, and as such calculating/checking the MAC won't leak any information about what's within $C$.

Conversely, suppose we have MtE. Then he receives $C$, for which he believes $C=E(M||T)$, with $T=HMAC(M)$. Having decrypted $C$ to get $M′||T′$, he now has to work out how to calculate a MAC over $M′$. This is where the padding oracle occurs, because the decryption algorithm has to work out how much padding there should be, leaking information about the message.


Calculating ciphersize of Paillier, SSE and OPE If I have to encrypt a 32 bit plaintext in each of Paillier, SSE and OPE, how can I make an estimate of the ciphertext sizes respectively in order to reserve the amount of space in a database?

How to know how much space to reserve?  There are two ways:

Take an implementation of the scheme, encrypt a 32-bit plaintext, and see how long the resulting ciphertext is. This is the simplest approach.
Understand the scheme at a conceptual level, and then use your understanding of the algorithm to predict how long the ciphertext will be.

Since it sounds like you don't understand the schemes at a conceptual level, my recommendation is that you use the first approach.

Note that your question does not provide enough information to answer your question completely. Here's what I can tell you, given the information in your question:

Paillier. Suppose you want security equivalent to that of 2048-bit RSA (a reasonable level of security; anything much shorter won't be very secure). Then Paillier ciphertexts will be 4096 bits wide: twice the length of the length of $n$. That's because a Paillier ciphertext is a number $c$ modulo $n^2$ (i.e., $c$ is between $1$ and $n^2-1$).  Even if you just want to encrypt a 32-bit plaintext, the ciphertext will still be 4096 bits long.  I know, that is a downside, but that's just the way it is.
OPE. Order-Preserving Encryption (OPE) is not a single scheme; it is a goal for a scheme.  It's like the difference between "RSA" vs "public-key encryption"; the former is a scheme, the latter is a goal.  OPE is analogous to "public-key encryption", not to "RSA".  Therefore, I can't tell you how long the ciphertexts will be if you use OPE, because the length of the ciphertexts will depend which OPE scheme you use, and there are many proposed schemes for OPE.
SSE. I don't know what the acronym SSE refers to.  If SSE refers to Searchable Symmetric Encryption, then there's a similar situation: we can't tell you how long the ciphertext will be, because there are many SSE schemes out there, and without knowing which of those schemes you are intending to use, we can't tell you how long the ciphertexts will be.


Testing speed of symmetric vs asymmetric encryption and decryption using gpg I'm aware that symmetric is faster than asymmetric.

I want to test this, but my (obviously incorrect) tests show the reverse.

Symmetric test:

#!/bin/bash

echo create random 100Mib binary file
head -c 100M /dev/urandom > blob

echo encrypt
time gpg --symmetric --batch --passphrase 123 --output blob.gpg blob

echo decrypt
time gpg --decrypt --batch --passphrase 123 --output blob blob.gpg

Asymmetric test (using fred's 4096 bit keypair, generated by gpg):

#!/bin/bash

echo create random 100Mib binary file
head -c 100M /dev/urandom > blob

echo encrypt using public key
time gpg --encrypt --recipient fred --output blob.gpg blob

echo decrypt using private key
time gpg --decrypt --batch --output blob blob.gpg

Results:

encryption : symmetric  : 6.2s
encryption : asymmetric : 5.8s         # I expected this to be > 6.2

decryption : symmetric  : 2.5s
decryption : asymmetric : 1.4s         # I expected this to be > 2.5

Can someone spot my error?

100 MiB is nothing nowadays. Still, it is likely that most time is spend because of I/O operations, rather than encryption /  decryption. Once the file is buffered in RAM, the operations will proceed much more quickly. Worse than that, during encryption most of the time is spend during compression of the input - not encrypting it. Try -z 0 so compression of random data doesn't cost that much time:

maartenb@maartens-ryzen:~/Test$ time gpg --symmetric --batch --passphrase 123 --output blob.gpg -z 0 blob
gpg: AES256 encrypted data
gpg: encrypted with 1 passphrase
gpg: handle plaintext failed: General error

real    0m0.686s
user    0m0.670s
sys     0m0.016s
maartenb@maartens-ryzen:~/Test$ rm blob
maartenb@maartens-ryzen:~/Test$ time gpg --decrypt --batch --passphrase 123 --output blob blob.gpg
gpg: AES256 encrypted data
gpg: encrypted with 1 passphrase

real    0m1.056s
user    0m0.965s
sys     0m0.088s

It seems that you are using password based encryption for "symmetric encryption" while you are using encryption / decryption with an unprotected private key (because the passphrase is cached).

For password based encryption you'd use a password based key derivation function or PBKDF, which has an explicit work factor (or iteration count) to slow down password guessing. More information here.

Now, if you look at the encrypted packet, you get this:

maartenb@maartens-ryzen:~/Test$ gpg --list-packets blob.gpg
gpg: AES256 encrypted data
gpg: encrypted with 1 passphrase
gpg: decryption failed: Bad session key
# off=0 ctb=8c tag=3 hlen=2 plen=13
:symkey enc packet: version 4, cipher 9, s2k 3, hash 2
    salt 4D975A3A5174CD4F, count 65011712 (255)
# off=15 ctb=d2 tag=18 hlen=6 plen=104857656 new-ctb
:encrypted data packet:
    length: 104857656
    mdc_method: 2

Note the s2k 3 and the pretty high value of count in there. Note that I'm using gpg (GnuPG) 2.2.12.

The public / private key operations do not have such a deliberate slow down - unless the private key is still protected by a password.

This is another advantage of public key encryption: during encryption you won't have any slow down to protect pass phrases sampled from a source with low entropy output (i.e. you).


Why is the function $f$ one of the inputs of the verification algorithm in homomorphic signature? As we known, a homomorphic signature scheme consists of the usual algorithms $(\text{KeyGen} , \text{Sign} , \text{Verify})$ as well as an additional algorithm $\text{Evaluate}$ that “translates” functions on messages to functions on signatures. If $\sigma$ is a valid set of signatures on messages $m$, then $\text{Evaluate}(f, \sigma)$ should be a valid signature for $f(m)$.

In several papers I read, the evaluation algorithm is defined as
$$\sigma' \gets \text{Evaluate}(pk, \tau, f, \vec{\sigma})$$
and the verification algorithm is defined as
$$0 \text{ or } 1 \gets \text{Verify}(pk, \tau, m, f, \sigma')$$
such that for every messages $\vec{m}$, every tag $\tau$, there is
$$ \text{Verify}(pk, \tau, f(\vec{m}), f, \text{Evaluate}(pk, \tau, f, \vec{\sigma})) = 1$$
I want to know why $f$ is one of the inputs in the algorithm $\text{Verify}$.

Why cannot we the define the verification algorithm as
$$0 \text{ or } 1 \gets \text{Verify}'(pk, \tau, m, \sigma')$$
such that for every messages $\vec{m}$, every tag $\tau$, there is
$$ \text{Verify}'(pk, \tau, f(\vec{m}), \text{Evaluate}(pk, \tau, f, \vec{\sigma})) = 1$$

I think that homomorphic signature schemes are similar to homomorphic encryption scheme. In homomorphic encryption schemes, the decryption algorithm does not use $f$ to decrypt the ciphertext. If the verification algorithm needs $f$, how can we verify correctly if the signatures are calculated by the evaluation algorithm for more than once?

The function $f$ is part of the input to $\mathsf{Verify}$, because the goal of homomorphic signatures is to compute authenticated functions on signed messages.
In particular, given a message $z$ and a signature $\sigma_z$, we want to not only verify that $\sigma_z$ is a valid signature for $z$, but moreover that $z$ is the output of some function $f$ applied to some inputs signed under some tag $\tau$.

To take an example from this paper, you can think of the tag $\tau$ as being "grades" and a list $(m_i, \sigma_i)$ being a bunch of individual grades separately signed under tag $\tau$. Homomorphic signatures now enable the owner of these signed individual grades to compute a signature $\sigma_z$ that attests that some value $z$ is indeed the average of the grades $m_i$.

This authenticity requirement is in stark contrast to (fully) homomorphic encryption, where you only want the ability to alter ciphertexts, but make no requirements on the authenticity of the produced encryption.

A notion that may be closer to what you are looking for are so called Malleable Signatures (see Def. 3.1), which are defined by the algorithms $\mathsf{Keygen}, \mathsf{Sign}, \mathsf{Verify}, \mathsf{SigEval}$, where the first three algorithms are defined exactly as in any standard signature scheme.
The algorithm $\mathsf{SigEval}$ takes as input $(\mathsf{pk}, f, \vec{m}, \vec{\sigma})$, where $\mathsf{pk}$ is a public key, $f$ is a function, $\vec{m}$ is a vector of messages, and $\vec{\sigma}$ is the vector of corresponding signatures.
It outputs a new signature $\sigma'$ such that $\mathsf{Verify}(\mathsf{pk}, f(\vec{m}), \sigma') = 1$.

Note that if you do not want to authenticate the computed function, then it may also not be necessary to use tags in the definition of your signature scheme.


How were the arbitrary values used inside SHA-256 determined? As I study SHA-256, I wonder how the values inside the algorithm were determined.
Take a look, for example, at how the 16-64th Words are generated. (in Java language)
    for (int j = 16; j < 64; ++j) {
        int s0 = Integer.rotateRight(words[j - 15], 7) ^
                Integer.rotateRight(words[j - 15], 18) ^
                (words[j - 15] >>> 3);

        int s1 = Integer.rotateRight(words[j - 2], 17) ^
                Integer.rotateRight(words[j - 2], 19) ^
                (words[j - 2] >>> 10);

        words[j] = words[j - 16] + s0 + words[j - 7] + s1;
    }

Just why were the values such as 15, 7, 18, 3, 2, 17, 19, 10, 16, and 7 chosen? Are these just arbitrary values that were randomly chosen for no reason? Or were these each chosen so that the algorithm is as difficult to reverse as possible?
    registers[7] = registers[6];
    registers[6] = registers[5];
    registers[5] = registers[4];
    registers[4] = registers[3] + temp1;
    registers[3] = registers[2];
    registers[2] = registers[1];
    registers[1] = registers[0];
    registers[0] = temp1 + temp2;

Also, in the main iteration loop (snippet shown above), why is the temp1 added to register[3]? Is that also just arbitrary or was it chosen for a particular reason?
Edit:
To rephrase the question without code and with equations, I'll put it another way.
In the equations to determine $W_t$ (for 16 <= t <= 63), you use the equation
$$W_t = \sigma_1 (W_{t-2})+W_{t-7}+\sigma_0 (W_{t-15})+W_{t-16}$$
Where
$$\sigma_0(x) = {ROTR}^{7}(x) \oplus {ROTR}^{18}(x) \oplus {SHR}^3(x)$$
$$\sigma_1(x) = {ROTR}^{17}(x) \oplus {ROTR}^{19}(x) \oplus {SHR}^{10}(x)$$
(according to FIPS PUB 180-4)
So, my question is, why were the arbitrary numbers in these equations chosen? The displacement of the word index by 2, 7, 15, and 16 appears to be random, but is there a reason to it? For the definition of $\sigma_0$ and $\sigma_1$, why were the arbitrary numbers 7, 18, 3, 17, 19, and 10 chosen?
The same question could also be asked about the main iteration loop, where $\Sigma_0$ and $\Sigma_1$ are used, which have just as arbitrary values in them.
As for the other question, it asks, why is it that $e = d + T_1$ in the loop from t=0 to t=63. It could have been placed in any of the other 6 working variables. Was it randomly chosen that $d$ would be the variable that has $T_1$ added to it?

In $W_t = \sigma_1 (W_{t-2})+W_{t-7}+\sigma_0 (W_{t-15})+W_{t-16}$

The $16$ is the number of 32-bit words in a SHA-256 block. It is here so that, when we consider $W$ as an array of $16$ rather than $64$ words (as most hardware and many software implementations do), the equation become adding to $W_{t\bmod 16}$ a feedback term $\sigma_1 (W_{t-2\bmod 16})+W_{t-7\bmod 16}+\sigma_0 (W_{t-15\bmod 16})$.
The $-2$, $-7$, $-15$ controls how far back in the formerly produced values of $W$ the feedback terms are taken from.

The $-15$ is as far back as it can go, given the $-16$. That maximizes the memory involved in the feedback.
The $-2$ indexes into a recently produced word (second only to what $-1$ would give), which promotes fast diffusion, and splits short-term feedback into two flows (even and odd indexes); also $-1$ could be a bottleneck to parallelization.
The $-7$ indexes somewhere else near the middle of the 16-word array, is odd so as to mix said two flows faster that $-15$ would ultimately do, and is slightly biased towards recent production, perhaps to promote faster diffusion.
Note: That later terms does not go thru a $\sigma$ function, contrary to the other two; that alternates XOR and addition (modulo the wordsize) in the feedback loop.

The shifts values are more difficult to justify. The pattern gives good diffusion, much better than a haphazard choice would do. But many other choices would be possible, and I can't pinpoint a selection process such that the choice made would be optimal.