Is it possible to successfully encrypt/decrypt in DUKPT using different sized BDKs? We are having our P2PE Solution validated against the PCI P2PE standard.  We currently use a TDEA 2-key based BDK, and IPEK in both the encryption and decryption environments.  ANSI X9.24-1 (2009) states that the BDK can be either 2-key or 3-key and the QSA is insisting that the BDK must be TDEA 3-key as per Appendix C in the standard. Our encryption environment can't perform encryption using TDEA 3-key (hardware limitation).  The assessor has asserted that mixed sizes of BDKs can be used with DUKPT, based on his reading of ANSI X9.24-1 (2009). Is that true?  Can DUKPT encrypt plaintext with an IPEK derived from a 2-key BDK and successfully decrypt that data from that same IPEK in a decryption environment with a 3-key BDK?

As this is symmetric key encryption the key used to encrypt the data must be used to decrypt the data so if a double-length TDES key encrypted the data, the same double-length TDES key can decrypt the data. A triple-length TDES key cannot decrypt data encrypted by a double-length TDES key and vice versa.

The P2PE requires that the minimum length for a TDES key be triple-length, i.e. 192-bits (168-bit excluding parity). However, if implemented as part of a DUKPT key management scheme, the TDES keys may be double-length. This is detailed in the footnotes of Appendix C.


Implementing AES-CBC (Matasano Crypto Challenge 10) I am currently doing the Matasano Crypto Challenge to learn a bit about cryptography. In that specific challenge one had to implement AES in CBC mode. I did that and verified that encryption and decryption are working using these test vectors. I can't manage to decrypt the message given in the challenge though. I am not asking you to decrypt it, but when I thought about it a bit more I got a bit confused due to the used IV (which is 0x00 for each byte). Doesn't this IV have no effect at all since the decrypted message just get's XORed against the IV? Shouldn't decryption also be possible using simple AES-ECB?

EDIT:
Sourcecode in Java: http://pastebin.com/cX8YZjD0

I suppose you have removed the base64 decoding, so you are working on the raw data.

Then indeed the first block is decrypted as if we were in ECB-mode, because after decrypting the first block, we xor with the IV, which is all 0 and indeed has no effect.

However, the IV for the next block will be the original previous ciphertext block. So after decrypting that block we have to xor with this new IV, so there we cannot suffice with just ECB mode. See also this picture from the comments:


Is this PRG secure? Different on halves of input So yes, this is a homework question, but no I have not just copy pasted the question without giving it any thought.

The question goes:

  $H$ on input $x$ outputs $G(x)$ except for $x$ when $x_\text{Left} = x_\text{Right}$, then $H$ outputs $0^{2n}$ for $n = |x|$. Is $H$ a secure PRG for all secure PRG $G$? On even length binary inputs.

So I am going with no it is not secure, BUT in a size $n$ input, $1/(2^{n/2})$ of the input, the outcome will be $0^{2n}$ for $n = |x|$. So, as $n$ grows, the amount of input that is distinguishable (where the input is symmetric).

$1/(2^{n/2})$ is a negligible function, so does this fall under negligible, so H is secure?

The PRG $H$ is still secure, and your intuition is right: $x_\text{Left} = x_\text{Right}$ happens with a very small probability, so this shouldn't be a problem.

The way to formally prove this would be as follows. Consider a distinguisher $\mathcal{D}$ and the experiment in which a random $x\in\{0,1\}^n$ is chosen and $G(x)$ is given to $\mathcal{D}$, we want to see that the probability that $\mathcal{D}$ outputs 1 in this case is very close to the possibility that $\mathcal{D}$ outputs 1 when we feed it with a truly random string $r\in \{0,1\}^{2n}$. Let $\text{eq}$ denote the event in which $x_\text{Left} = x_\text{Right}$ (where $x$ is the uniform seed of the experiment), then we know that

\begin{multline}
\operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1] \\ = \operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1 | \text{eq}]\operatorname{Pr}[\text{eq}] + \operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1 | \text{eq}^c]\operatorname{Pr}[\text{eq}^c] \\ = (\operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1 | \text{eq}] - \operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1 | \text{eq}^c])\operatorname{Pr}[\text{eq}]\\ + \operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1 | \text{eq}^c]
\end{multline}

So

\begin{multline}
|\operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1] - \operatorname{Pr}[\mathcal{D}\left(r\right) = 1]| \\ \leq \operatorname{Pr}[\text{eq}] + |\operatorname{Pr}[\mathcal{D}\left(G(x)\right) = 1 | \text{eq}^c] - \operatorname{Pr}[\mathcal{D}\left(r\right) = 1]|
\end{multline}

The first term is negligible as you mentioned, and the second is because of the assumption that $G$ is a PRG, since whenever $\text{eq}$ does not occur, the experiment is the same as the experiment for $G$.


How can I show RSA-OAEP is not IND-CCA secure if G always outputs 0 (i.e. there is no hash function)? Here is what I understand the algorithm to be:

Let $G, H$ be one-way functions, where G outputs the 0 string.

Select a random $$-bit integer $$.
Pad out $$ with $0$s to length $=||−.$
Compute $=()⊕_{}$ (i.e. $X = _{}$)
Compute $=⊕()$
Return $||$

Compute $r = Y \oplus H(X)$
Compute $m_{padded} = X \oplus G(r)$ (i.e. $m_{padded} = X$)
Strip off the $0$s from $X = _{}$ to recover $$

IND-CCA Game

The IND-CCA game in this case is as follows:

The adversary selects two messages $_0,_1$ and submits them to a decryption oracle $O$.
The decryption oracle samples $∈\{0,1\}$ and computes $*= \textrm{RSA-OAEP}(_)$.
The adversary is free to perform more decryptions, except for the one condition that $O(c∗)$ will return $⊥$.
To conclude, the adversary must guess $$ corresponding to the message that was encrypted.

Work towards showing that algorithm is not IND-CCA secure

The adversary need only recover $X$ from $c$, where $c = \textrm{RSA_OAEP}(m_b) = \textrm{RSA}(X||Y)$. Very basic question, but is $m_b \in \{b||m_1, b||m_2\}$? If so, then the adversary would know that $X||Y$ differs by $|X|$ significant digits depending on the value of $b$. However, $Y$ will always differ since $b$ is random, so $c = \textrm{RSA}(X||Y)$ will also always differ.

Unsure of where to go from here, any help would be much appreciated!

The adversary wants to output either the plaintext or $\bot$. For RSA-OAEP, $⊥$ is output when either the adversary tries to decrypt $c*$, or if the first half of the padding is not the 0 string then the decryption fails. Could we try multiplying $m_0 = 0...0$ and $m_1 =$ random with $2^e$ mod $N$?

$b$ is random

Yes, but it is random in the set $\{0,1\}$. $b$ reflects the coin toss made by the decryption oracle / challenger in the IND-CCA game to decide if s/he encrypts $m_0$ or $m_1$ at the second bullet.

  Does $m_b \in \{b\mathbin\|m_1,\ b\mathbin\|m_2\}$ ?

No in general, and that holds even if we fix the indices to be in $\{0,1\}$ rather than $\{1,2\}$. The intended meaning of $m_b$ is:
$$m_b=\begin{cases}m_0&\text{if }b=0\\m_1&\text{if }b=1\\\end{cases}$$
otherwise said, $b=0\implies m_b=m_0$, and $b=1\implies m_b=m_1$. Thus $m_b \in \{m_0, m_1\}$ with no concatenation involved. Note: the IND-CCA game allows to choose the two messages $m_0$ and $m_1$ equal, but that's a silly move.


Construction of a MAC with decryption mode of a block cipher Assume we have a hardware device with build-in AES decryption and support for ECB and CBC mode (but no support for AES encryption). It only receives data and decrypts it. Minor modifications of the hardware are still possible, but you can't add AES encryption.

Now assume we want to add a MAC for ensuring integrity. CBC-MAC can't be used, as it requires the encryption mode of the block cipher.

Are there MACs you can construct with only the decryption mode of a block cipher?

I thought about using the CBC-MAC scheme and simply replace the AES encryption with the AES decryption, but I'm not sure this would result in a secure MAC.

A block cipher is a (strong) pseudorandom permutation. As such, it makes no difference if you compute it in the forward or in the backward direction. Thus, you can use AES in decryption mode and it has exactly the same security as AES in encryption mode, as a block cipher. Therefore, you can do CBC-MAC with AES decryption and you are fine.

Two remarks:

Make sure you use an independent key for the CBC-MAC (and not the same as the encryption), and
You should use CMAC and not straight CBC-MAC.


Digital signatures in SSL/TLS-like protocols The TLS protocol includes an optional Server Key Exchange message that is signed by the server. It seems to me that this message is digitally signed only to prove to the client that the message originated from the server.

The general purpose of a Digital Signature is to provide a proof of origin that can be verified by anyone at any time, without any prior communication with the signer. Providing such a proof to the client regarding the origin of the Server Key Exchange message is overkill, in the sense that it might require the client and server to implement Digital Signature generation and verification algorithms that might be redundant.

Wouldn't the following alternative provide a similar proof, and in addition be reducible to the CDH problem?

Presume the client $C$ and server $S$ share a set of parameters defining a group $G$, suitable for Diffie Hellman, and that $C$ already has the public key $y \equiv g^x \in G$ of the server.

$C: $ Generates random $a,v$ and $A \equiv g^a$ and $V \equiv g^v$ and sends $A,V$.

$S: $ Generates a random $u$ and $U \equiv g^u$, calculates $premasterkey \equiv V^u$ and $k \equiv A^x$ and $H = HMAC(k,U)$ and sends $U,H$.

$C: $ Calculates $k' \equiv y^a$ and verifies that $HMAC(k',U) = H$. If OK, calculates $premasterkey' \equiv U^v$; otherwise aborts.

(Note: The random values of the Hello messages as well as the Finished messages should be added for completeness.)

The above protocol should require one less modular exponentiation calculation client side compared to the DHE_DSS cipher suites defined in TLS, would only require the implementation of the DH algorithm for $G$, but would on the other hand not allow the server to precalculate the DSA $r$ values.

Is there any other reason to use a digital signature in the Server Key Exchange message, than the order of the protocol steps being put there because it wouldn't matter much for DHE_RSA how it is done (digital signature in Server Key Exchange or an extra key transport message sent by the client earlier)?

So what you are doing here are two Diffie-Hellman key exchanges in parallel – one with the server's static Diffie-Hellman key pair $(x,y)$ and the client's ephemeral key pair $(a,A)$ to calculate $k = k'$, and one with completely ephemeral keys to calculate the actual pre_master_secret. $k$ is only used as a MAC key to authenticate the server's exchange message.

  Presume the client $C$ and server $S$ share a set of parameters defining
  a group $G$, suitable for Diffie Hellman, and that $C$ already has the
  public key $y≡g^x∈G$ of the server.

This second condition is not realistic in many circumstances – i.e. not for the normal WWW usage, where you often want to connect to a server you don't know beforehand.

In this case we would then use the same way as now – deliver the server's public key $y$ together with a certificate (chain) which proves that the key belongs actually to the server we want to connect to.
To check these certificates, the client would need to implement a signature verification algorithm anyways. The existing DH_DSS and DH_RSS key exchange types work just this way, by the way, for their static Diffie-Hellman key (but there is just one exchange, not two).

Then, how could we fit this into the TLS handshake protocol?
We have these messages sent by the participants:

  Client                                               Server

  ClientHello                  -------->
                                                  ServerHello
                                                 Certificate*
                                           ServerKeyExchange*
                                          CertificateRequest*
                               <--------      ServerHelloDone
  Certificate*
  ClientKeyExchange
  CertificateVerify*
  [ChangeCipherSpec]
  Finished                     -------->
                                           [ChangeCipherSpec]
                               <--------             Finished
  Application Data             <------->     Application Data

The ClientHello message doesn't really have space for the messages $A$ and $V$ to be sent – even less since at this point the cipher suite isn't even selected.
We could put something in the Extensions part, but I think this is not what they were made for.

The server's next bunch of messages has the selection of the Cipher Suite (including the key exchange protocol) in the ServerHello, so from here one the server can send related messages. So here we would send the server's static public DH key $y$ in the Certificate message (inside a certificate).

The client would then send in its ClientKeyExchange its two public keys $A$ and $V$.

We now see the problem: There is no more place for the next message from the server where he would send $U$ and $H$, since the Finished messages are more or less only a MAC of the handshake messages with the master secret as a key, and the client's Finished is even sent before the server one's (and already encrypted with the negotiated keys).

But if we look again more detailed, we see that actually $U$ is not depending on anything what the client sent us, so the server can send it already in the first step, in the ServerKeyExchange message, just after $y$ and its certificate.

Sending $H$ (the MAC for $U$ using $k$ as a key) is not really necessary, as the Finished message from the server side has a similar function. What would be necessary instead would be to incorporate $k$ (i.e. the server's certified DH key pair) somehow into the pre_master_secret. Simple concatenation of $V^u = U^v$ and $k = k'$ should do here (the master secret is then derived using a PRF, including the random values from the Hello messages).

So the final key exchange protocol would look like this (omitting the stuff which is not relevant for the actual key exchange, like ClientHello, ServerHello, ServerHelloDone):

$S$:

send $y = g^x$ (with certificates) in Certificate,
send $U = g^u$ in ServerKeyExchange.

$C$:

check certificates for $y$,
send $A = g^a$, $V = g^v$ in ClientKeyExchange,
calculate $P = y^a||U^v$, $M = PRF(P, …)$ (this is the master secret),
use $M$ to derive the encryption/authentication keys,
switch on encryption (ChangeCipherSpec),
send $F_C = PRF(M, C, …)$ in Finished.

$S$:

calculate $P' = A^x||V^u$, $M' = PRF(P, …)$, $F_C' = PRF(M', C, …)$,
check $F_C \stackrel{?}= F_C'$,
use $M$ to derive the encryption/authentication keys,
switch on encryption (ChangeCipherSpec),
send $F_S' = PRF(M', S, …)$ in Finished.

$C$:

calculate $F_S = PRF(M, S, …)$
check $F_S \stackrel?= F_S'$.
Start sending application data.

This actually is a hybrid between the DH_anon and the DH_* key exchange types. And if the server's public key is already known to the client, we can omit the Certificate message and/or the certificate checking.

  Is there any other reason to use a digital signature in the
  Server Key Exchange message, than the order of the protocol
  steps being put there because it wouldn't matter much for
  DHE_RSA how it is done (digital signature in Server Key Exchange
  or an extra key transport message sent by the client earlier)?

The DHE_RSA and DHE_DSS key exchange protocol needs a signature in the Server Key Exchange message, since there is no other way for the client to verify that the message (and the public DH key) actually comes from the right server. In the DH_RSA and DH_DSS key exchange protocols, instead the (static) public key is contained in the server's certificate (which itself also contains a signature, but usually one created long before).

In our new protocol (i.e. my variant of your protocol), we don't need a signature, and still succeeded to fit it into the TLS handshake order.


Do a 160-bit SHA-1 hash and a 160-bit slice of a SHA-256 hash have the same strength in terms of collision-free? Take OpenPGP fingerprint for example. If the 40-digit hex standard remains unchanged, would it be helpful to upgrade SHA-1 to SHA-256 (but only taking the last 160 bits), in terms of reducing the risk of collision?

SHA-1 is broken in practice in terms of finding collisions. This shattered attack (identical-prefix collision attack) requires roughly $2^{63.1}$ SHA-1 evaluations and this is approximately 100,000 faster than finding collisions with generic birthday attack on 160-bit output that has $2^{80}$- time complexity. That is, for a hash function with $\ell$-bit output we expect at least one collision with a 50% probability within $2^{\ell/2}$ outputs.

There are no attacks on SHA-256 trimmed to 160 bit better than the generic collision attack due to the birthday attack. Therefore they are not the same in finding collisions, in this case, SHA-256 trimmed to 160-bit has better security than SHA-1.

The attacks on SHA-256 or similarly other iterated hash functions are performed on reduced rounds. We don't expect weakness on the trimmed version of well designed cryptographic hash functions. Except for the resistances which happens naturally. If such a weakness exists, it can represent a weakness in the designs of the hash function and this could be used to attack the full version.

Note that NIST deprecated the use of SHA-1 in 2011 way before the actual attack. 160-bit hash output is no longer considered secure. If you consider that Bitcoin miners reached $\approx 2^{92}$ double SHA-256 hashes per year in 06 Agust 2019, 160-bit is no longer secure, or even 180-bit. The hash rate $2^{92}$ for a year is for the double SHA-256 hashes. Therefore they can calculate $2^{93}$ SHA-256 in a year.

note: I've re-check the current hash rate of Bitcoin miners, it is was 80.294 Exa Hashes/s (1 exa is one quintillion (1,000,000,000,000,000,000) ) in 06 Agust 2019. It reached 110.6056 Exa on 23 October 2019, unfortunately, or hopefully, this is still $\approx 2^{92}$. In a second, this makes $2^{67}$ double SHA256 calculations which means, they can break the DES key less than a second or any 64-bit block-cipher.


Zero-knowledge proof that a group element is a quadratic residue? In a paper it says: "To convince a verifier that a group element is a quadratic residue, the prover executes the following proof with the verifier":

$PK \left\{ (\alpha) : y = \pm g^\alpha \right\}$

Does someone know how such proof is implemented by a signature proof of knowledge? The group is an RSA group $\mathrm{G} = \mathrm{QR}_n$ with $n = p \cdot q$ and two safe primes $p$ and $q$. I have found an implementation as part of a bigger protocol but although the $\pm$ was in the $\mathrm{PK}$ statement, they ignore it in the implementation. Now I am a little bit confused.

First let's develop a zero knowledge interactive proof. The verifier doesn't know $p,q$ as otherwise he could just take the roots. Let $a$ be the putative residue, and have $P$ know a square root $t$. So P will take a random number $r$ and send $r^2$ to V. V will send a bit, either $0$ or $1$. If $0$ P sends $r$ to V. If $1$ P sends $rt$ to V. This is zero-knowledge by a standard simulated transcript argument. It is a proof of knowledge because P must assure that $r^2a$ is a quadratic residue, and it is enforced that he must send a square.


Elligator based on TweetNaCl TweetNacl is all-in-one crypto library. It's very easy to use, so I often include it in my projects;

But recently I need to use Elligator, I had to use LibElligator. It would be very usefull to have Elligator func in TweetNacl.

I am not a cryptographer so it's hard to me to undersand internals of both libs.
Is it posible to implement elligator hashing based on math of TweetNacl?

It's certainly possible, although it will be very slow.

TweetNacl includes all the required field arithmetic operations. The main thing you will have to implement is the Chi function.

If you don't understand the internals and how these functions work, I would recommend using libsodium instead. It has a compatible API, and supports hash-to-point using Elligator.


Boolean Circuits vs Arithmetic Circuits I am just wondering what's the differences between boolean circuits and arithmetic circuits? I know the basic notions of circuits. My question is their applications in cryptography. For example, why we should consider them separately (e.g., why we should consider functional encryption for boolean circuits and functional encryption for arithmetic circuits separately)?

I cannot find any literature that explain this clearly currently. If you have read such literature, please tell me.

Boolean circuits and arithmetic circuits are two different ways of representing a computation. The main difference is with respect to their input types and their gate types: boolean circuits work on bit inputs, and the gates of the circuit correspond to boolean operations (such as XOR, AND). On the other hand, arithmetic circuits work on inputs that are elements of some field $\mathbb{F}$, and the gates of the circuit correspond to arithmetic operations, id est, field operations (such as additions and multiplications).

The class of functions that can be computed by Boolean circuits of polynomial size coincide with the class of functions computable by arithmetic circuits of polynomial size. Indeed, one can always use some representation of the field elements and translate the field operations to boolean operations (with a blow-up polynomial in the length of field elements). Conversely, one can always translate a boolean circuit to an arithmetic one, by interpreting $0$ as the neutral for addition over $\mathbb{F}$, $1$ as the neutral for multiplication over $\mathbb{F}$, and translating the boolean gates to arithmetic operations (e.g. $a\phantom{i}\mathsf{OR}\phantom{i}b$ becomes $a + b - a*b$).

Deciding whether a boolean circuit is better than an arithmetic circuit in a particular application depends on the type of computation you want to perform. In cryptography, it is quite common to rely on computation on-field elements, and we have cryptographic tools that allow us to manipulate field elements in an atomic way, id est, treating a given field element as a single input (and not as a string of bits). In this case, it makes sense to represent the computation with an arithmetic circuit. However, many applications of, say, secure computation involve non-arithmetic operations (for example, integer comparison, which is a basic procedure in many computations). In this case, implementing this non-arithmetic operation as an arithmetic one would be very inefficient, and boolean circuits are more natural representations.

Another way of seeing it is the following: arithmetic circuits are a generalization of boolean circuits to arbitrary fields; boolean circuits correspond to arithmetic circuits over the field $\mathbb{F}_2$. There have been many papers that worked on extending cryptographic methods that work well for computations represented as boolean circuit to the setting of computations which are best captured by arithmetic circuits, to get efficiency improvements for those circuits (e.g. Yao's garbled circuit method has been extended to garbled arithmetic circuits), or on bridging between methods adapted to boolean circuits and methods adapted to arithmetic circuits, to capture computation whose best representation is a mix between the two.

Answering a question in comments

  I am looking for a reference that establishes the result that "the class of functions that can be computed by Boolean circuits of polynomial size coincide with the class of functions computable by arithmetic circuits of polynomial size". Can you provide a reference to a book or a scientific paper? My search was without success...

As I mentioned in the comment, you will likely not find a reference because the result is folklore. Fix an arbitrary field $(\mathbb{F}, +, \cdot)$ and consider a function $f$ which can be computed by a boolean circuit of size polynomial in its input size, say, over the standard basis $\{\mathsf{XOR}, \mathsf{AND}, \mathsf{NOT}\}$. To emulate the computation over $\mathbb{F}$, encode the bit $0$ as $0_\mathbb{F}$ (the neutral for addition in $\mathbb{F}$) and the bit $1$ as $1_\mathbb{F}$ (the neutral for multiplication). The boolean gates can be emulated as follows:

To compute an $\mathsf{AND}$ gate on input $(x,y)$, return $x \cdot y$
To compute an $\mathsf{XOR}$ gate on input $(x,y)$, return $x + y - 2\cdot x\cdot y$
To compute a $\mathsf{NOT}$ gate on input $x$, return $1_\mathbb{F}-x$.

I'll let you check that this correctly emulates the boolean operations. Since emulating each boolean gate requires at most 4 arithmetic operations, the arithmetic circuit emulating the boolean circuit over $\mathbb{F}$ is of polynomial size as long as the boolean circuit is polynomial size. The converse direction is trivial since a boolean circuit is just an arithmetic circuit over $\mathbb{F}_2$.

For the sake of generality, I'll add that you can generally emulate field operations over an arbitrary field $\mathbb{F}$ using boolean circuit; indeed, this is what your computer is doing every day: fix a field $\mathbb{F}$, and consider the binary decomposition of any element $x$ of $\mathbb{F}$: $x = \sum_{i=0}^{\lceil \log |\mathbb{F}| \rceil-1} b_i \cdot 2^i$, with $b_i \in \{0_\mathbb{F}, 1_\mathbb{F}\}$.

To emulate addition over $\mathbb{F}$, use the schoolbook binary addition method, which only requires using $\mathsf{XOR}$ and $\mathsf{AND}$ gates, by observing that $\mathsf{XOR}$ gives you the $i$-th value, while $\mathsf{AND}$ gives you the $i$-th carry.
To emulate a multiplication over $\mathbb{F}$, use the textbook multiplication algorithm, which relies only on $\mathsf{AND}$ gates plus field additions, which we already showed can be emulated.

Overall, the size increase is dominated by the $O(\log^2 |\mathbb{F}|)$ cost for the schoolbook binary multiplication.


Finding $x$'s parity in the discrete log problem Suppose $p$ is prime, and $g, a\in\mathbb F_p$ are given elements with $g$ a primitive root. The discrete log problem poses the task of finding an integer $x$ such that $g^x=a$. Show that even if $x$ cannot be recovered, one can check if $x$ is odd or even by inspecting the element $a^{(p-1)/2}$.

I'm not sure how to approach this question. I tried $g^{x(p-1)/2} = a^{(p-1)/2} = 1$.

Any help would be appreciated! Thanks.


Can Skein be used as a secure MAC in format H(k || m)? Can Skein be used as a secure MAC in format H(k || m)?

I understand it can work with HMAC, but it is fine as a one-pass MAC in the format above and resists length extension attacks. Is this assumption correct?

One of the Skein authors mentions that Skein has another MAC construction with a security proof in their paper, but I can't find it. Does anyone know how that works?

Length extension attack

The reason why $H(k \mathbin\| m)$ is insecure with most older hashes is that they use the Merkle–Damgård construction which suffers from length extensions. When length extensions are available it's possible to compute $H(k \mathbin\| m \mathbin\| m^\prime)$ knowing only $H(k \mathbin\| m)$ but not $k$. This violates the security requirements of a MAC.

Like all SHA-3 finalists Skein does not suffer from length extensions, so this attack does not apply.

State collision attack

There is also a potential attack based on state collisions where an attacker searches for a pair of messages which collide for all (or at least many) keys. This does not work for the sequential mode of Skein when computing $H(k \mathbin\| m)$, since it consumes the key before the message and the attacker thus doesn't know the internal state when the message gets hashed.

This attack applies in theory when using $H(k\mathbin\|m)$ in the treed mode of Skein since only the first node will have key dependent state and state collisions in other nodes can be searched for without knowledge of the key. This also applies to $H(m\mathbin\|k)$ in the sequential mode.

But since Skein has a 512 bit internal state, finding collisions by brute force costs $2^{256}$ operations, which is ridiculously infeasible.

Still collisions are usually the first property to fall to advancing cryptanalysis, so I have more confidence in MACs where this attack is not applicable at all, instead of merely being infeasible.

Built in MAC mode

Skein has a built in MAC mode, where the key is passed in as a separate parameter. The way it consumes the key is pretty similar to $H(k\mathbin\|m)$ but it doesn't simply concatenate them.

This mode has a few advantages over the simple $H(k\mathbin\|m)$:

It cleanly separates the domains of key and message
The initial state depends on the key for all nodes in a tree, not just the first
The key is consumed before any other parameter
The authors supplied an explicit security proof for this mode.
You can cache the state after consumption of the key improving performance for fixed keys (but reducing performance for single use keys). You can achieve a similar effect by padding the key to 512 bits (the block size) with $H(k\mathbin\|m)$, but implementations are unlikely to have support for that.

Properties 2 and 3 mean that the state collision attack does not apply even if you use some of Skein's additional features.

Unfortunately not every implementation includes the keyed Skein feature.

Conclusion

$H(k\mathbin\|m)$ is secure as MAC. But it's preferable to use the built in MAC mode where available, especially if you use any advanced Skein features such as trees.


Certificateless cryptography Implementation Hello guys I am trying to implement Certificateless Cryptography algorithm with reference to this base paper. Right now I am trying to implement the code in java. There are some points specified in PDF which I didn't understood. I need some help to understand how should I implement them.

The points are as follows (kindly correct me if I misunderstood any point):

  Pick a generator of $g$ of $Z_p^*$ with order $q$. -> for this step I just followed this link as reference and calculated $g$ as $g^{(p−1)/2}\bmod p=1$
  where $g$ is prime number.
  Choose cryptographic hash in the paper they have specified that they had used SHA-1 to generate hash. I can generate the hash values
  but I am not able to reproduce the hash functions given in base paper,
  does $(0,1)^*$ is used to represent binary.
  Hash usually generates hexadecimal values do I need to convert them into decimal for Raise operation i.e. power
  Does the hash needs to be of fixed size or not.
  Sorry to say but in summary I didn't understood the encryption part of this paper. I know stackexchange is not made to explain how it works
  but I just want a proper guide line so that I can implement the
  application.

As far I understood the paper (very briefly) it looks like it's talking about the default asymmetric encryption without the CA (certificate authorities). However - it seems there's the SEM part of the system which seems to know the private keys (???) and acts as the revocation authority.

I believe you can use the default Java crypto API without needing to implement it yourself. In fact I'd discourage you to do that until you REALLY know what are you doing, how/what to properly encrypt with the public key, etc. For the start - I'd advice to learn something about the cryptography elements and implementations, what you see in the papers are mathematical models of common crypto elements.

As it goes for your questions:

  Pick a generator of g of Z∗p with order q. -> for this step I just
  followed this link as reference and calculated g as g(p−1)/2modp=1
  where g is prime number.

It means to choose you keysize (so - e.g. 2048 bit keys) and generate a private key (p, q) and public key (p*q). Using a KeyPairGenerator should be effective.

  Choose cryptographic hash in the paper they have specified that they
  had used SHA-1 to generate hash. I can generate the hash values but I
  am not able to reproduce the hash functions given in base paper, does
  (0,1)∗ is used to represent binary.

Any reasonable hash function will do - so lets assume SHA-1. All numbers are binary for the computer, its only their 'human' representation how you can display them (decimal, hex, ..)

  Hash usually generates hexadecimal values do I need to convert them
  into decimal for Raise operation i.e. power

Hash returns a bit array (byte[]), you can use the BigInteger class to raise it to certain power. Don't forget all operations are under the discrete group  (so you do ($g^a$ mod p). About the steps described in the paper - you need to 'sign' the hash. And after the decryption, the signature is compared with a newly computed signature so data integrity is ensured.

As for the topic - I'd advice to spend some time understanding the default cryptography and asymmetric encryption (for this case) and usage practices and it will be much easier for you to follow the paper. The problem with the cryptography is that something is misunderstood or neglected, it will completely break the security.

In all cases - have fun :)


How are timestamps verified? You put an input and the hash value comes as an output then when someone puts the input the hash function it is applied to see if it is the same hash original value is stored in some database , that is how it works if I remember it correctly.

However  I am having some trouble understanding timestamps now,
I have just used a timestamp service, univerisign.

I sent the file to timestamp it and I believe the input is the  file and the date and by using sha512 it creates  a document signature, this is exactly what has done:
My document was example.pdf:

  Title

  testing the document.

and after using the service, it appears example.pdf:

  Title

  04_02-2012

  testing the document.

It also comes a file called example.pdf.ers wich I believe It is the hash value but
How can I prove the validity of a document timestamped by Universign?

This is how the web answers it:

  Universign uses the timestamp protocol defined by the IETF RFC 3161
  standard. You can use any software compliant with this standard to
  check your timestamp seal.

What does this mean?

How different is my example.pdf document from a fake one fake.pdf with the same date written on it?
Does my example.pdf have any security characteristic or is it just a normal pdf document and all the verification information it is stored in example.pdf.ers?

I think that if universign was able to gave me a proof of the document, a smart one could easily create a fake proof of the document by giving  the fake input including the date,
maybe It is got to do with the credentials of the organization in this case universign as not all timestamps are valid and probably example.pdf.ers is saved in universign.eu database and that is why it is valid.

Note that my question although long it is specific I just tried to answer it while formulating it, It is all about understanding the verification of timestamps.

Actually Universign produces "Evidence Records" as described by RFC 4998. Evidence Records in turn rely on standard time stamps which RFC 3161 is about. Evidence Records can embed several nested time stamps; this is used for long-term archival, when you want time stamps to remain verifiable beyond the end-of-validity of the certificate of the time stamp authority, or even when one of the hash functions which were originally used becomes broken. Evidence Record Syntax (ERS) includes provision for regular maintenance, namely spraying a new layer of paint (a new time stamp) whenever needed.

As a general basis, a time stamping authority (TSA) works like this: it receives a document hash, and applies a digital signature on a structure which contains the hash value and the current date -- the date is measured by the TSA, not provided by the client. The signature, when verified, "proves" that the TSA was involved, and since we trust the TSA for having a well-maintained clock and never signing any structure for which it did not write the current date itself, this proves that the document hash existed since the announced date (at least). Hash functions being nominally impervious to preimages, this in turn demonstrates the existence of the document at that date.

The cornerstone of the trust is the "honesty" of the TSA, which, administratively speaking, goes through certifications. Various institutional bodies verify, through audits and procedures and mountains of paper which required whole forests to be cut down, that the TSA has been developed and is maintained with enough security, in a way which can be audited. In the case of Universign, they can boast such certifications as can be obtained from French government; in effect, France says: "their time stamps are good enough, that they can be used as proofs in legal proceedings, the burden of proof lying on whoever is arguing against the validity of said time stamps". This can be assumed to more or less extend to the rest of Europe, at least in the near future (the legal systems for electronic signatures and time stamps are slow to spread, but Europe is trying to push them in an harmonized way -- as always, things work differently in America, so the legal status of Universign timestamps in a US court is much less guaranteed).


Regex searchable word list for space-less monoalphabetic substitution I am working on teaching myself basic cryptography. In the process I created a simple substitution cipher based on a single alphabet, and a statically defined offset (no key for now). Now that everything is working, I want to start on another application to "crack" the offset. The key here is my cipher removes all spaces, so I can't judge the length of the individual words.

To solve this issue I would like to use regular expressions. I would then take parts of the (possibly) deciphered message and query a word list to determine where the words start and end.

Is this a good way to do this?

I know there are only 26 possibilities for the offset in my simple cipher. However, I would like to find the answer programmatically.

The simple shift sounds like a Ceasar Cipher.

The simplest crack for this is probably frequency analysis. The most common letter in the English language is E. Count your letters, and guess your shift based on that.

If you want to make it better, you could get the X most common letters in your cipher, calculate what you think the shift is, and compare that to known letter frequencies in English, like ETAOIN SHDRLU. The frequency guess that differs the least (with the lowest edit distance) is probably your candidate.

You can also judge how good the resulting text is by using bigram and trigram frequency tests.

You may also find some of the methods described in these books helpful:
http://www.nsa.gov/public_info/declass/military_cryptanalysis.shtml

UPDATE: It sounds like what you're actually trying to do is detect when you've decoded your ciphertext. You don't necessarily need to match the words in a dictionary to do that.

The above mentioned methods should work quite well, especially if you start using bigram and trigram frequency.

If you get to the point where you need a more sophisticated method to detect when your text is decrypted, I suggest asking on Stack Overflow, and also telling them what your current approach is, and why it's not working for you.

Note that regular expressions are not useful for what you have in mind. A Markov chain would be a much better tool, especially since it can be used to predict where a word has ended and a new word has started.


Determining the Shamir's secret sharing scheme for the following problem I'm having trouble solving the Shamir's Secret Sharing scheme for the following problem that states:

  Problem: A certain military office, which is in control of a powerful missile, consists of six generals, five colonels, and four desk clerks. Describe how they would set up a Shamir scheme so that any five generals or any set of four colonels and three desk clerks or any three generals and three desk clerks can launch the missile.

I was thinking that this looks like the Shamir's scheme definition where the secret S was divided among the three groups( $n=3$? ), and so I need to describe the process of obtaining the threshold scheme $(k, n)$, the $k$ shares from the given problem? Or am just confusing myself further. Any help of approaching this problem would be helpful.

Each person might be allotted more than one share of the secret.

Let $G$, $C$ and $D$ denote the number of shares allotted to a General, a Colonel, and a Desk Clerk respectively, and let $T$ denote the Threshold of the secret sharing scheme.  Then, we have that
\begin{align}
T &\leq 5G,\\
T &\leq 4C + 3D,\\
T &\leq 3G + 3D.
\end{align}
Can you find suitable values for $G,C,D$,and $T$? The total number of shares is
$N = 6G + 5C + 4D$ and we have a $(T,N)$ secret sharing scheme.

     $D=2, C=3, G=4, T=18$, and $N = 47$ seems to work. There are, of course, other combinations that would result in $18$ or more shares, e.g., $5C+2D$ or $4G+D$ but nothing in the problem statement says that this is not to be allowed. Note that the $5$ colonels (or the $4$ Desk Clerks for that matter) cannot stage a coup by themselves; the colonels have to have at least two Desk Clerks (or a General) as co-conspirators.

Addendum: in the spirit of @IlmariKaronen's answer,

Divide the secret $S$ into 6 shares in a $(5,6)$ secret-sharing scheme and give each of the six generals a share. Any 5 of them can reconstruct $S$.
Create a random binary vector $X$ as long as the secret $S$, and then make five shares of $S\oplus X$ in a $(4,5)$ secret-sharing scheme, giving one share to each colonel. Any four of them can reconstruct $S\oplus X$. Create $4$ shares of $X$ in a $(3,4)$ secret-sharing scheme and hand one share to each desk clerk. Any $3$ desk clerks can reconstruct $X$, and together with $S\oplus X$ from the $4$ colonels, $S$ can be reconstructed.
Create $6$ shares of $S\oplus X$ in a $(3,6)$ secret-sharing scheme and hand a share to each general. Any three generals can reconstruct $S\oplus X$, and together with $X$ from three desk clerks, can recreate $S$.

Note that this has have fewer secret-sharing schemes to implement than Ilmari's method, and the desk clerks and colonels have only one share to have and hold. Only the generals have two different shares and must remember to use the correct one in the two different cases when they are acting by themselves and when in conjunction with three desk clerks. Also, the desk clerks, by themselves, can only reconstruct $X$.


List of big strong primes I want to make a Diffie Hellman key exchange code using Python, but I'm afraid of just randomly picking $g$.

I read on the answer of Thomas Pornin to this question How does one calculate a primitive root for Diffie-Hellman?, that if you use a strong prime, then every number on the group (except $1$ and $p-1$) would have an order of either $p-1$ or $\frac{p-1}{2}$, but I can't find anywhere online a list of big strong primes to use. Anyone knows where can I find one?

Edit: thanks for the generous help of fgrieu I realized I am looking for safe primes, and not strong primes.

In cryptography, strong primes have been used (with various definitions of that) for RSA, in order to defeat the factorization of the public modulus by Pollard's p-1 and p+1 algorithms, and various other attacks. For this reason, there is no list of standard large strong primes, for that would defeat the purpose in RSA, where the prime factors of the public modulus must be secret.

The Diffie-Hellman key exchange often uses safe primes, which is a prime $p$ such that $\displaystyle q=\frac{p−1}2$ is also a prime. The answer linked to in the question accidentally misuses the word strong prime where safe prime is meant, as noted in comment.

Standard safe primes for use in DH are in RFC 3526. These intentionally use the generator $g=2$ for the subgroup of prime order $\displaystyle q=\frac{p−1}2$. Except perhaps for the 1536-bit one, they are considered large enough to be safe for use right now.

  With (safe prime $p$), can I use any number between $2$ and $p−2$ and be guaranteed to have an order of either $p−1$ or $\displaystyle\frac{p−1}2$ ?

Yes. Argument: the order of a subgroup always divides the order of the group, which is $p-1$ for prime $p$. When further $p$ is a safe prime, the order of the group is $2\,q$ with $q$ prime, thus the order of any $g$ is one of $1$, $2$, $q$ or $2q$. Only $1$ has order $1$ and only $p-1$ has order $2$.

But as noted in comment, there is no good reason not to use the generator coming with the prime.


Shamir's Secret Sharing Scheme - prime security? Does the prime (which needs to be larger than the message) have to be chosen randomly for security, or can it just be a huge constant?

Also, the Wikipedia article for SSSS states

  The size of each share does not exceed the size of the original data.

but isn't each share comprised of both $X$ and $Y$? or is $X$ already known because of the prime? and if the prime is chosen at random then surely the prime has to be distributed with each share?

The prime can be just any prime, so it doesn't have to be chosen randomly (but of course it can). And the prime is made public, so it is not part of the shares. Public values are known by definition by everyone, therefore are not part of the shares.

But you're right, the quote is wrong about the size of the share, because it neglects $x$. However, it's really close, because $y$ is usually the same length as $p$ (uniform distributed), but $x$ can be chosen to be small.


what is the public information in Elliptic curve cryptosystems Currently my knowledge about Elliptic curve is quite limited to the textbook and I don't know how a practical Elliptic curve cryptosystem works.

I read an example about key exchange using Elliptic curves. And I am wondering what is the public information (key) of a practical Elliptic curve cryptosystem.

First, the equation of the Elliptic curve should be public.
How about other parameters? Such as the order of the curve ( number of points on the curve), the generator point of the curve and so on.

Can you give me a good reference about how a practical Elliptic curve cryptosystem works?

Thanks in advance.

To generate your pair of keys with elliptic curves first you have to chose your domain parameters (I think this name may comes from the P1363 naming convention, or perhaps it's previous).

Those domain parameters will be public. For example for curves over finite fields those parameters are: ${p,a,b,G,n,h}$. The lower level operations will be made in $\mathbb{F}_p$ and the operations will be made using points on a curve. Then $a$ and $b$ (or the equivalents is uses different notation) is also public and also the equation used. About the generator point $\langle G\rangle$, you can think like public it is in DLP over finite fields.

About the order of the cyclic subgroup of points where the ECDLP is defined is public ($ord(G)=n$), together with the cofactor $h$ (that shall be very small number and both primes, with relation $h \lll n$), and the product of them is the number of points of the curve.

The only thing secret is the secret key, often labelled as $d$, where the public key is $P=d[G]$.


Please explain parameters of RFC5639 Elliptic Curves including brainpoolP160r1 RFC 5639 brainpoolP160r1 has

p = E95E4A5F737059DC60DFC7AD95B3D8139515620F (Wolfram Alpha says prime)

A = 340E7BE2A280EB74E2BE61BADA745D97E8F7C300

B = 1E589A8595423412134FAA2DBDEC95C8D8675E58

x = BED5AF16EA3F6A4F62938C4631EB5AF7BDBCDBC3

y = 1667CB477A1A8EC338F94741669C976316DA6321

q = E95E4A5F737059DC60DF5991D45029409E60FC09 (Wolfram Alpha says prime)

h = 1

I do not understand why h = 1 yet q < p. I thought that if you had a prime field size then there is only one cyclic subgroup in size equal to the field size (c.f. Lagrange). This doesn't seem to be the case for brainpoolP160r1

The order of the curve $\#E(\mathbb{F}_p)$ is different from $p$. In fact, according to Hasse's theorem, $\#E(\mathbb{F}_p)=p+1-t$ where $t$ the Frobenius trace satisfies $|t|<2\sqrt{p}$. So the gap between $\#E(\mathbb{F}_p)$ and $p$ is at most $2\sqrt{p}$. Note that, if $\#E(\mathbb{F}_p)=p+1$, $\textit{i.e.}$ $t=0$, the curve is supersingular. For brainpoolP160r1, the order is 1332297598440044874827085038830181364212942568457 (160-bit). You can play with sage code:

p = 0xE95E4A5F737059DC60DFC7AD95B3D8139515620F
A = 0x340E7BE2A280EB74E2BE61BADA745D97E8F7C300
B = 0x1E589A8595423412134FAA2DBDEC95C8D8675E58
x = 0xBED5AF16EA3F6A4F62938C4631EB5AF7BDBCDBC3
y = 0x1667CB477A1A8EC338F94741669C976316DA6321
E = EllipticCurve(GF(p),[A,B])
G = E(x,y)
G.order()
E.order()


creating PKCS8 private keys with a PBMAC1 hash PKCS#8 provides two encryption schemes (PBES1 and PBES2) and one message authentication scheme (PBMAC1). It seems like a combined method (eg. authenticated encryption) would be ideal but whatever.

Anyway, my question is...  are there any tools in the wild that can create a PBMAC1 PKCS#8 encoded private key?

The man pages for OpenSSL make me think that OpenSSL doesn't support this:

https://linux.die.net/man/1/pkcs8

Your link (2898) is actually PKCS5 which defines those two encryption schemes (with predefined cases for 1) and the MAC scheme. PKCS8 uses the ASN.1-flexible way (AlgorithmIdentifier) to identify the encryptionAlgorithm, but for specific values references the older PKCS5 v1.5 which had only the scheme now called PBES1 and PBKDF1. OpenSSL also supports the PBES2/PBKDF2 schemes from PKCS5 v2 and the PBE schemes defined in PKCS12 (see below).
PKCS8 does not support a separate authentication algorithm. All defined PBES1 and PBES2 schemes and most pkcs12PBE ones do use CBC mode with padding, which provides some protection against accidental corruption but not tampering.

PKCS12 is now the more common and arguably better way of transporting privatekeys plus usually related certificate(s). It does have a PBMAC on the whole container (technically optional but usually present) and PBE on the KeyBag and CertBag items in the container; even though certificates shouldn't need to be secret, by convention (or just custom) the CertBag is encrypted with weak 40-bit encryption, although OpenSSL has an undocumented option -certpbe none to leave it clear. PKCS12 originally referred to the older PKCS5 (effectively PBES1/PBKDF1) and added its own PBE/PBKDF scheme again with several predefined cases, plus its own PBMAC scheme. PKCS12 v1.1 changes this to prefer PBES2/PBKDF2 from newer PKCS5 for encryption while still documenting its own PBE schemes in Appendix C for backward compatibility, and still using its own PBMAC scheme.

If I had to speculate why the need for integrity protection wasn't appreciated at first, it might be that by 1990 most industry experience had been with wrapping symmetric keys, mostly for transport -- rarely storage, which was in special hardware instead -- and that customarily used a manually verified Key Check Value.


Definition of symmetric cipher and definition of asymmetric cipher So I'm currently taking a cryptography class right now and my professor has told the class that she can't even define symmetric cipher for us without getting into asymmetric ciphers and the textbook we use hasn't been helpful. It gives me five points: plaintext, encryption algorithm, secret key, ciphertext, and decryption algorithm.

I was just wondering (plus I've googled around, there didn't seem to be much helpful definitions of these) could anyone please help define what exactly a symmetric cipher is? And if possible, an asymmetric cipher?

Thanks!

In simplest terms:
Symmetric encryption
Symmetric encryption uses the same key for encryption and decryption.
This key is called "secret key", because it has to be kept secret at all times or else someone could decrypt the encrypted message.
Examples of symmetric encryption:

AES
Vigenère

Asymmetric encryption
Asymmetric encryption uses one key for encryption and a different key for decryption.
The key for encryption is public knowledge and is called "public key". The key for decryption on the other hand is kept secret and called "private key". This is to ensure that only the possesser of this private key can decrypt a message, that has been encrypted with the corresponding public key.
Examples of asymmetric encryption:

RSA
Diffie-Hellman (Actually here the asymmetric part is the key-exchange and not a full encryption of a message.)


Does “SHAttered” only work for PDF files? It appears that SHA-1 is broken in practice.  The website detailing this attack shows an infographic of how two PDF files can have the same SHA-1 hash value.  Also Google's.  I've also read Mathew's answer regarding the implications of this, and his explanation example focuses on PDFs.

What is it with PDFs?  Does the attack only work on them exclusively?  A PDF is just a sequence of bytes arranged in some order specified ages ago by Adobe Inc.  I would have thought then that any two arbitrary file types could be attacked and hashed to the same value, not just PDFs.

The current version of the SHAttered website has an image that describes the structure of the attack, relative to the PDF.  I believe under fair use we can reproduce the image below:

So the collision blocks reside inside a JPEG image inside the PDFs.  JPEG file formats are a complicated topic, but modern software supports a variety of metadata in JPEGs—this is for example how cameras store the date and time that a photo was taken, the GPS coordinates where the photo was taken, camera settings that were used, pre-rendered thumbnails for quicker display at small resolutions, etc.  So you can create JPEGs that look exactly the same (same image data) but different metadata; and evidently you can also exploit this property to create JPEG files that look different but have the same SHA-1 digest.


File encryption with AES CTR mode I understand that encrypting files in CTR mode is not perfectly safe, because it potentially leaves the files open for cryptanalysis, if the attacker has access to previous versions of the same files. But is this really feasible when we are talking about encrypting files?

Lets say we got a program that reads and writes encrypted files with AES CTR mode. If we have a word document it will be written to many times, and therefore change alot without the key and counter changing for specific blocks.

Now how feasible is it really for an attacker to actually find these previous versions on a given harddisk? Should this constellation not be reasonable secure against anyone except maybe the NSA?

There's nothing wrong with using CTR mode to encrypt files, or anything else, as long as you make sure to use every nonce value only once. (And add authentication, if malleability would be a problem.) You could, for example, rewrite the whole file encrypting it with a new random nonce every time it's modified.

Since you are assuming nonce reuse, an attack that used different versions of the file would indeed be simple. How feasible it is depends on how easy those previous versions are to get to, which depends on what sort of threats you envision. An attacker who does see multiple versions does not need NSA-level powers.

Example attacks:

An attacker who can read the encrypted file e.g. daily would be able to just wait until you modify it.
If there are backups or a versioning filesystem, an attacker could find previous versions there.
Access to the raw HDD image might make an attacker able to read previous versions from currently unused parts of the filesystem.

Etc. None of these is really that difficult, if the attacker has proper access.


TLS_PSK and perfect forward secrecy My question is about how difficult is for someone having compromised the PSK and sniff all (DT)LS handshake, (so getting the NONCE), to get the encryption keys?

I understand :

getting the pre-master secret is straight forward

but then, what about the master secret MS?

because MS is calculated with PRF_HMAC_SHA256 which generates different MS for each sessions , how easy can it be for an attacker to re-calculate the right MS, then the encryption keys?

Assuming you are talking TLS_PSK without DH or RSA (which are an option), if an attacker compromises the PSK and watches the nonces go past in the clear, yes the attacker can easily compute the master secret.

Section 2 of RFC4279 details how the premaster secret is computed. Without DH or RSA, there is no, indeed can be no*, additional entropy added.

The master secret is a function of the premaster secret and two nonces sent in the clear at the beginning of the handshake. So if the handshake is captured, so are the nonces. So all the inputs to compute the master secret are known.

* Any additional entropy that could be added must be shared. TLS_PSK assumes that the PSK is the only shared secret value between the two parties.


What is the most secure encryption algorithm that keeps the entropy the same or even lowers it? On top of my mind comes caesar cipher, but that is not really secure

so what is the most secure encryption algorithm that doesn't affect entropy or even lowers it?

I know this might not be as secure as normal encryptions, but I'm asking about what is the most secure among these types of encryptions?

basically I have a series of bytes, and I want to encrypt them in a way that a machine that only checks the entropy to detect encryption gets bypassed. so basically this encryption doesn't affect the entropy, or even better if possible, lowers it.

I thought maybe I can just replace each byte with another, but was wondering is there any better method? keep in mind that security is my second priority and keeping or lowering entropy is my number one priority

This seems pretty simple if your 'isEncrypted' distinguisher looks for a cipher text entropy rate in excess of 7 bits byte. But it's not exactly an encryption. Just hex encode it.

All good cipher text is computationally indistinguishable from perfectly pseudo random.  Take the most securely encrypted cipher text from any decent algorithm.  It will be 8 bits/byte if occupying all the bits within a byte.  Then hex encode it to ASCII base 16. You now need two bytes to encode any single original byte of cipher text. Ergo the entropy rate has been halved to only 4 bits/byte and you still maintain maximum security. Your message would of course get correspondingly longer.

In extremis, go to UTF-32 binary encoding which could just be a series of two really funky characters.   Perhaps two Egyptian Hieroglyphs of your choice, each occupying 4 bytes. Mean entropy rate = 0.25 bits/byte.


Why do key fobs/garage doors openers use rolling codes instead of PGP or SSL encryption? Wouldn't they be more secure if they used the same encryption technology computers use for remote access?

I can think of several issues with using PGP or TLS:

Both PGP and TLS require certificate management (unless password based), it would be tricky to get a PKI going for this;
PGP and TLS are overkill for key fobs / garage doors and would put unnecessary strain on the choice of processor and battery;
PGP and TLS require access to a secure random number generator, which is also pretty expensive to put in a key fob.
The TLS handshake requires two way communication;
Both TLS and GPG require intricate implementation of the message protocol (stuff you can do without for a door opener).

Even from a technical standpoint TLS is overkill; you're really just interested in authenticating a command that cannot be replayed. This explains the choice of a rolling code I guess.

Those are the technical reasons. I guess most of the manufacturers aren't that IT savvy either. They might not even know about PGP or TLS. They're more likely to be interested in motor & hinge design and picking the right color for your door.

That said, there's likely some kind of home automation that can

open a door and
uses some kind of transport protocol or message authentication.

I doubt if these two "heavy weight" protocols are used towards the door though.


On Program Verification Through zk-SNARKs Can you provide an example use case of program verification using zk-SNARKs that explains:

What it actually means to verify the execution;
What are the implication of this new technology;
How does it work, because at moment I still haven't understood the difference between zk-SNARKs and proofs that can be generated with asymmetric cryptosystems, since they also are zero-knowledge. Are zk-SNARKs just more general? If so can you provide an example use case that highlights what can be done with zk-SNARKs that instead can't be done with asymmetric cryptosystems?

I think the simplest and the best example for a system which uses zk-SNARKs to verify execution of a computation (program) is the Pinocchio system, developed by Microsoft and IBM research groups. You can get access to their source paper, which has some examples, in this URL.

With regard to your questions; the meaning of verifying an execution is that you check that the computation of your target program or circuit has been done correctly. E.g. assume you have a program $P(.)$ and you need to run this program with some inputs, e.g. $x$. Due to some reasons (e.g. low power device, save money) you outsource the computation and ask some cloud computing services (e.g. Amazon service, Google, Microsoft) to execute this program with this input for you and return the result. The cloud executes the program with your input $x$ and returns $y=P(x)$ to you. But if you do not trust the server, you are not convinced that $y$ is the correct answer for $P(x)$. To deal with this issue, the cloud (service provider) needs to give a formal proof that the execution of $P(x)$ is done correctly.

Note that outsourcing computation makes sense only if checking the proof generated by service provider is easier (lighter) than recomputing $P(x)$ by verifier himself.

zk-SNARKs such as Pinocchio uses pairing-based cryptography which makes the proof size very short (less than 1KB) and proof verification very efficient for verifier (client), verification time is around 0.1 second on current smartphones or laptops.

To get a clear view about how zk-SNARKs are used to prove that an execution of a circuit is done correctly, I strongly recommend to look at Pinocchio system. For a quick overview check the following Slides. At a very high level, the following figure shows what steps Pinocchio system (that uses zk-SNARKs) takes to give a proof for a computation.


What's the difference between word-oriented and byte-oriented ciphers? I am currently learning about the RC4 cipher and its improved version called Spritz.

The paper of Spritz says

  We do not consider other stream-cipher proposals here, and expect that for many applications other word-oriented architectures may be a better choice than the byte-oriented RC4/Spritz style.

Now, what I don't quite understand:

What's the difference between a word-oriented and a byte-oriented cipher/algorithm?
When should either a word- or byte-oriented cipher be used, and
What are the advantages/disadvantages of each?

I found some papers that introduce a byte- or word-oriented cipher, but without elaborating clearly what's the idea behind it. To my surprise, googling for "word oriented byte oriented" and checking several Wikipedia pages on computer architecture/CPUs didn't really yield useful results to me.

To my understanding the only difference between word oriented and byte oriented is that word length depends on the processor used, so maybe 32 bits or 64 bits long, for example.

The idea of a word oriented cipher is that it uses native operations to hardware, processing words instead of bits, making for higher speeds, but clearly that makes designs technology dependent which may not always be the best way to go. Mixing addition mod $2^{16}$ with $GF(2)^{16}$ and multiplication mod $2^{16}+1$
can be complex to analyze. Thus word oriented operations have a complex algebraic representation which may be considered a plus for the designer, but then reliable analysis of such operations also hampers the designer.


Plotting Running Times of SAT solver In the the paper "Efficient Methods for Conversion and Solution of Sparse Systems of Low-Degree Multivariate Polynomials over GF(2) via
SAT-Solvers" there is a Figure that I can not understand and I need help to understand it. The authors plot the running time of the probability distribution of the SAT solver applied to a certain problem. My question is about the X axis. Why there are numbers in this Figure 1, that are placed in vertical form? How to interpret this axis X?

I imagine that are interval times but I do not understand why they are in vertical form. Moreover, on the same axis there are twice the number 180.

Disclaimer: I'm answering without any knowledge on the content of the paper in question.

  Why there are numbers in this Figure 1, that are placed in vertical form?

Because otherwise the figure would not fit into the page width (or the authors would have to use unreadably small font).

  How to interpret this axis X?
  I imagine that are interval times but I do not understand why they are in vertical form. Moreover, on the same axis there are twice the number 180.

What you imagine is most probably correct. The vertical form I explained above. This is not 180 but 1800 (the second time). After 990 goes 1030, not 103. The last zero is either lost or simply omitted to save space because it is assumed to be obvious for a reader that "After 990 goes 1030, not 103".


How do I convert an elliptic key signature r and s value into a signature byte array? I have an existing system that signs an arbitrary binary blob with an ECDSA key. The output of this is an r and s value. I now need to verify this signature on another system. On this other system though we are using BouncyCastle, and would prefer to just use the byte array verify method.

Unfortunately my cryptographic mathematical skills are not up to parr and I don't know how to convert my r and s values into a byte array for the signature. How do I do this conversion?

You can choose between two signature formats. One is the most common one and has been defined by the ANS(I) X9.62 standard in ASN.1:

ECDSA-Sig-Value ::= SEQUENCE {
  r  INTEGER,
  s  INTEGER
}

which is then encoded using DER TLV encoding.

For ASN.1 / DER the INTEGER values are encoded as are variable sized, signed two-complement, big endian encoded values. For instance number 255 is encoded as 00 FF (00 is required so it is not interpreted as a negative value) and 256 is encoded as 01 00.

Bouncy Castle has an ASN.1 / DER encoding / decoding facilities build in. Probably easiest is to find out where they encode their own $r$ and $s$ values to generate the usual ECDSA signature.

The other often used method is to simply concatenate the $r$ and $s$ values. In that case the signature is:

$$\operatorname{I2OSP}(r, l) \mathbin\| \operatorname{I2OSP}(s, l)$$

where $l$ is the number of octets required to encode the field size of the group. Or, put differently, $l = \big\lceil \mathrm{keysize} / 8 \big\rceil$. I2OSP has been defined, for instance, in the RSA standards and explained here. The outcome is two statically sized, unsigned, big endian numbers simply concatenated together.

This scheme is often used for smart cards, embedded computers or other schemes that require a minimum size of a signature such block chain.


For the symmetric-key encryption algorithm, is it possible to use the exponent and modulo to be the keys For example:

Encrypt with: $M^{k_1} \bmod k_2$

where $M$ is message, $k_1$ and $k_2$ are independent keys

If it is possible, what is the decryption algorithm?

Thanks!

I don't think 'mod' can be reversed, so it is not possible.
Consider k1 = 2, k2 = 6.
Now,
M = 1 => C (ciphertext) = 1.
M = 5 => C = 1

You have no way of knowing whether the cleartext was 1 or 5, as you get the same ciphertext for both.


Different inner and outer hash functions for NIST-recommended HMAC? The NIST recommended HMAC uses

$$\operatorname{HMAC}_k(\mathrm{text}) = H_\mathrm{out}( (k \oplus \mathrm{opad}) \mathbin\| H_\mathrm{in}((k \oplus \mathrm{ipad}) \mathbin\| \mathrm{text}) )$$

Is it feasible to analyze the security and efficiency with different hash function implementations for $H_\mathrm{in}$ and $H_\mathrm{out}$ for a single instance?

I would like to know whether it makes sense to use different hash functions for the same HMAC.

You may want to take a look at the original HMAC paper by Bellare, Canetti and Krawczyk (1996), or at the new security proof by Bellare (2006).

As far as I can tell at a glance, there's nothing in either of these proofs that would actually rely on the inner and outer hash functions being the same function, as long as both of them satisfy the appropriate security properties.


Practical Uses for Timing Attacks on Hash Comparisons (e.g. MD5)? Consider the following code snippet:

<?php
session_start();
if (md5($_POST['password']) === '550b1f8802ca3d7a987fc46a2af408c3') {
         $_SESSION['loggedIn'] = true;
}
header("Location: /");
exit;

If an attacker doesn't know the hash, they should still be able to leak bits of the hash via timing information (and by knowing the hashing strategy employed).

If you send thousands of requests and study the MD5 hash you transmit (as well as the timing information) of various passwords, you should be able to deduce the first N hexits of the hash. Then, using a client-side brute force search against this known information, optimize your online guessing by discarding a large number of guesses.

Even deducing the first 4 bytes can cut your guess time down by a factor of a billion.

That said, has anyone published any research in this area? Specifically, exploiting a partial leak via timing information and using it to guess passwords against unknown hashes faster.

Would this be worth researching at all?

There is no timing attack possible on MD5 as practically implemented on most platforms. That's because MD5 uses only 32-bit addition, 32-bit bitwise boolean operators, and constant rotations/shifts, which exhibit no data-dependent timing for any reasonable implementation, even written without consideration for resistance to timing attacks.

There is however a conceivable timing attack, unrelated to MD5, on the code shown (which is PHP, but that holds in many other languages, with minor variants), aiming at finding the first few characters of the hash value if that's unknown (the equivalent of the constant 550b1f8802ca3d7a987fc46a2af408c3 in the code sample). Assuming the string comparison of === is performed from left to right, character by character, and stopping on the first non-matching character, there can be a timing attack on the string comparison: if on average the password test1 (hashing to 5a1…) is rejected significantly slower than test0 (hashing to f6f…) and test2 (hashing to ad0…), then the true hash of the password can safely be assumed to starts in 5. We can then find and time the rejection of other test passwords which hash starts in 5 (like test8 hashing to 5e4…) to try find the second character of the hash; and so on. In this way we need to perform (significant) timing measurements for at most 32×16 well-chosen test passwords in order to find the whole hash.

That's fine in theory. In practice the attacker trying this will face at least two hurdles:

The difference in timing is very small, and a variety of things will conspire to mask it: network delays, other tasks and how they left the various CPU caches, numerous clocks on the hardware..; in order to make any progress, the attacker will need an awful lot of measurements, a direct network connection, a low-load server, and a sound strategy (like considering the average of observed times for a given test password after some setup-dependent filtering, perhaps keeping the few lowest measurements if all the accidental masking factors are additive).
Finding the leftmost $n$ characters of the hash requires about $2^{4n}$ evaluations of MD5 in order to find the test passwords to be timed; with $2^{60}$ evaluations (which is already requiring serious effort), the attacker only gets 12 characters (60 bits) out of 32 (128 bits).

If the first of these two hurdles can be overcome, the method has a benefit: the attacker can explore test passwords according to a synthesized list of candidate passwords approximately by decreasing likelihood, so that a low-entropy password will be found with (hopefully) fewer online queries to the server than without the timing attack; and no more offline hashes than required for a brute force attack with the hash known, even though the attack is performed without the hash.

I would be slightly surprised if that was a real threat for any server accessed through a few network hops; and I'm unsure this is worth academic publication in a first-tier conference or journal.


Are hash functions chaotic? I'm looking into "bitcoin like" mining processes. Say a security process uses a hash of data as proof that the data was known at some point in time.

From what I understand, hash functions are pseudorandomly generated based on the initial seed (the raw data).

If the hash function is chaotic, then the seed data should have strange attractors. If so, then I may be able to map a seed to its attractor and "pre-mine" using attractor buckets.

Are these pseudorandom functions "deterministic chaotic systems"?

No.  That's not going to help you.  The cycle structure of a random function is well-studied, and it doesn't help you break hash-chaining, "proof-of-work", Bitcoin, etc.  Crypto schemes already take into account the structure of (the graph of) a random function.  It's not going to help you "pre-mine" and get some speedup on breaking Bitcoin (for instance).

For instance, the graph of a random function $\{0,1\}^n\to \{0,1\}^n$ typically has the following form: there is a single large cycle of length $\Theta(2^{n/2})$, such that most inputs eventually lead to the cycle.  Starting from a random input, the length of the path that leads to that large cycle is typically $\Theta(2^{n/2})$.  This does not break standard schemes for hash-chaining, proof-of-work, Bitcoin, etc., as the parameters for their hash function is chosen to take this structure into account.

Whether you want to count this as "chaos" depends upon your precise definition of "chaos", which you haven't provided in the question.  Anyway, from a technical/scientific/engineering perspective, what label we assign it (chaos or not) is less important than the technical properties it provides and the security goals it can help to protect.


Are the following schemes based on a pseudo-random permutation secure? I am currently working on the following task:

Let F be a pseudorandom permutation.

Consider the encryption scheme for the message space $\{0, 1\}^n$ defined as follows: $Gen(1^n)$ chooses two random keys $k_1 , k_2  \in \{0, 1\}^n$. Encryption is done as $Enc_{k_1,k_2}(m) = F_{k1}( k_2 \oplus m)$  (Decryption is done in the natural way)

Does this scheme have indistinguishable encryptions in the presence of an eavesdropper? Is this scheme CPA-secure?

Consider the encryption scheme where the message space is $\{0, 1\}^{n/2}$ and encryption of a message $m$ is done by choosing random $r \leftarrow \{0, 1\}^{n/2}$ , and then outputting the ciphertext $F_k(r ||m)$. (Decryption is done in the natural way)

Does this scheme have indistinguishable encryptions in the presence of an eavesdropper? Is this scheme CPA-secure?

My current answers are:

This scheme has indistinguishable encryptions in the presence of an eavesdropper since $F$ is a PRP, and therefore $F_{k1}( k_2 \oplus m)$ will give a pseudorandom string. However I am not sure whether my intuition is correct.
The scheme should not be IND-CPA secure since encryption is deterministic.

This scheme is both IND-COA as well as IND-CPA secure. IND-COA since (as in 1.) $F$ is a PRP, and therefore $F_k(r ||m)$ will give a pseudorandom string. It's also IND-CPA secure as a random $r$ is used every time a message in encrypted.

Since I am not too confident about my solutions I appreciate any comments and/or corrections.

Looks rather OK to me.

As for the first question, XOR with a value won't introduce any duplicate values and now $F$ is a PRP the first part of the answer should be correct. It's clearly deterministic, so no IND-COA or CPA security.

As for the second question $F_k(r ||m)$ seems to me identical to a single block encrypt with CTR mode. However, for CTR mode you require quite a large block size.

You could well distinguish between $m=0$ and $m=1$ given enough ciphertext; you'd get a lot of 00 and 10 results if $m=0$ is prevalent, which would be different from the 01 and 11 results. Concatenation in general should be considered dangerous.

So I think it could be CPA secure, but only when $n$ is somewhere around 128 bits or higher and/or the amount of messages is restricted. Without additional restrictions the answer should be no IND-COA or CPA security. Learning that a particular value is prevalent is already enough to break IND-COA:

e.g from Wikipedia about ciphertext-only attacks:

  The ability to obtain any information at all about the underlying plaintext beyond what was pre-known to the attacker is still considered a success.


Why does the FBI ask Apple for help to decrypt an iPhone? The current debate of the FBI trying to get Apple to assist in decrypting an iPhone made me wonder:

Normally, upon turning on an iPhone, everything is decrypted using a 4-digit pin (or actually, a key that is derived from the PIN with a strong KDF, but that's not the point here). The key element of Apple's protection is a locking mechanism that locks or destroys the data upon 10 (or so) failed attempts.

What prevents the FBI from reading all data from the device (including any hardcoded data that may be encoded in chips or whatever) and perform the same decryption within their own environment? (…which does the same as Apple's implementation except for the self-destruction or locking feature.)

Brute forcing a 4 digit PIN is peanuts. The locking feature is not essential for the decryption process.

Is iOS's protection really just security through obscurity, or am I missing something?

(Android wouldn't be any different of course, I'd say everything that can be decrypted with a 4 or 5 digit pin instead of a strong password is fundamentally insecure).

I'll try to take a stab at this. From Apple's iOS Security Guide, we learn that

  The metadata of all files in the file system is encrypted with a random key, which
  is created when iOS is first installed or when the device is wiped by a user. The file
  system key is stored in Effaceable Storage. Since it’s stored on the device, this key is
  not used to maintain the confidentiality of data;

and

  The content of a file is encrypted with a per-file key, which is wrapped with a class key
  and stored in a file’s metadata, which is in turn encrypted with the file system key. The
  class key is protected with the hardware UID and, for some classes, the user’s passcode.
  This hierarchy provides both flexibility and performance. For example, changing a file’s
  class only requires rewrapping its per-file key, and a change of passcode just rewraps
  the class key.

In other words: By physically being in possession of the device, you should easily able to get the file system key (take out the SSD and read the key off it). Let's call the file system key $K_{FS}$. Additionally, every file $f$ is encrypted using a per file key $K_f$. To get $K_f$, we need to have the file system key ($K_{FS}$) and the "class key", let's call the class key $K_C$.

So, there's a function $F_1$ which given the file, file-system key, the class key gives you the file key. $K_f$ =$F_1(f, K_{FS}, K_C)$. That means that for the FBI to decrypt a specific file, they'd need:

$f$ ✅
$K_{FS}$ ✅
$K_C$ ❌

So they don't have $K_C$ afaik. Right, how do you normally get that class key? The document says, it's protected by the "hardware UID" ($K_{UID}$) and (sometimes) the user's passcode $K_P$. Alas, there's another function $F_2(K_{UID}, K_P)$ which given the hardware UID and (sometimes) the passcode returns you the class key.
Assuming the FBI can easily brute force the passcode ($K_P$), all they need is the hardware UID ($K_{UID}$) but unfortunately for them that is apparently put in the silicon and therefore hard to access:

  The device’s unique ID (UID) and a device group ID (GID) are AES 256-bit keys fused
  (UID) or compiled (GID) into the application processor and Secure Enclave during
  manufacturing. No software or firmware can read them directly; they can see only the
  results of encryption or decryption operations performed by dedicated AES engines
  implemented in silicon using the UID or GID as a key. Additionally, the Secure Enclave’s
  UID and GID can only be used by the AES engine dedicated to the Secure Enclave. The
  UIDs are unique to each device and are not recorded by Apple or any of its suppliers.
  The GIDs are common to all processors in a class of devices (for example, all devices
  using the Apple A8 processor), and are used for non security-critical tasks such as when
  delivering system software during installation and restore. Integrating these keys into
  the silicon helps prevent them from being tampered with or bypassed, or accessed
  outside the AES engine. The UIDs and GIDs are also not available via JTAG or other
  debugging interfaces.

  The UID allows data to be cryptographically tied to a particular device. For example,
  the key hierarchy protecting the file system includes the UID, so if the memory chips
  are physically moved from one device to another, the files are inaccessible. The UID is
  not related to any other identifier on the device.

So, if I read that correctly, the function $F_2$ seems to be implemented in hardware and is accessible as $F_2'(K_P)$. Note that $F_2'$ only has one parameter which is the user's pass code. In other words $F_2'(K_P) = F_2(K_{UID}, K_P)$, so the hardware UID is provided automatically by the hardware. In non-Secure Enclave iPhones (like the 5C), you can probably brute force it with a custom iOS version that let's you use $F_2'$ as often as you want. In a normal iOS, only the lock screen can presumably run $F_2'$ and prevents you from doing that without ever increasing delays (and potential eventual device wipe). With a Secure Enclave iPhone (5S, 6 (+), 6S (+)) the secure enclave prevents you from running this function repeatedly. So not even the iOS kernel can run $F_2'$ without any delays.

Given that the iPhone in question seems to be a 5C, the FBI only seems to need a special version of iOS from Apple which allows them to use $F_2'$ repeatedly without delays with automatically provided pass codes. That should give the FBI 10000 (assuming a 4 digit pass code) or 1000000 (assuming a 6 digit pass code) "class keys". They can then just try each of the class keys and one of them will give them the data.

It is irrelevant for this particular question but I think it would still be interesting: Does the Secure Enclave change anything here? At the first sight: Obviously yes because a new iOS version wouldn't be good enough because the Secure Enclave would prevent you from running $F_2'$ in a loop by brute forcing the pass code. BUT: The secure enclave runs some kind of firmware too, so this limit could probably be lifted but updating the Secure Enclave. So far it's unclear to me whether Apple can do that without wiping all the content from the Secure Enclave. Different sources claim different things. This article covers that. Especially it cites a tweet from John Kelley who was apparently formerly within Embedded Security at Apple. He claims

  [...] I have no clue where they got the idea that changing SPE firmware will destroy keys. SPE FW is just a signed blob on iOS System Part

In other words: Even with a newer iPhone Apple could just deploy a special firmware to the Secure Enclave (SPE) which would allow to run $F_2'$ as often as the FBI pleases.

I hope this helps. All the information is taken from the iOS Security Guide and my interpretation of it.

edit: Because of the comment how my answer answer the question I should indeed state that more clearly. IMHO the FBI asks Apple because the need to run  $F_2'$ very often without delays so they can brute force the iPhone's code. For the iPhone 5C a new version of iOS should be enough as only the OS prevents you from doing that (you don't have programmatic access to $F_2'$ without special privileges). For newer iPhones, the Secure Enclave does prevent that apparently. The FBI can't compile their own, hacked version of iOS without this restriction because the iPhone only runs code signed by Apple and the FBI does (probably) not have Apple's signing keys.

Please do comment if you know or think that I misinterpreted anything or got anything wrong.


Why can´t an attacker find the key if he has the plain text, the IV and the ciphertext? I am reading a book about web security and they are now talking about AES CBC.
After reading the chapter I was wondering, can an attacker compute my secret key if he has access to the IV, the plain text and the ciphertext.

Is this possible? If not why?

Thanks.

After reading the chapter I was wondering, can an attacker compute my secret key if he has access to the IV, the plain text and the ciphertext.

No; or at least, there is no known way to do so.

If there was, well, AES would be considered "broken".

  Is this possible? If not why?

Well, the short answer is "a lot of really bright people have tried to come up with a way, and nothing occurred to them".

In AES, the plaintext is processed by the key in a number of steps ("rounds" is the terminology we use), stirring in the key each time.  Each step is easy to reverse if you know the key (hence AES is invertible, and so we can decrypt with the key); however the end product (the ciphertext) is a complex function of the key and the plaintext; it certainly isn't an obvious way to figure out what key was used.

Now, there are more advanced strategies that could be used (such as looking at the encryption of similar plaintexts, and see if that gives you information you can't get by looking at isolated plaintext/ciphertext pairs), however AES was specifically designed to foil such advanced strategies (and would appear to be successful in doing so)


Can an Enigma-style cipher of sufficient complexity be considered secure today? Regarding the German Enigma machines, if I recall correctly, the reason they were defeated was because the Allies were able to generate a massive database of possible rotor settings, and because the day key was encoded twice in the beginning of each message.

Given that computers of today can simulate an Enigma-ish machine with an arbitrary number and complexity of rotors (for example, a rotor that only shows up every tenth character, or one that goes forward a different number each time), transmission errors are low, and binary data (not plain-text, but gzipped or base64'ed text) tends to beat frequency analysis, would it be possible to use an Enigma style cipher to encrypt data today, or would it be susceptible to similar pitfalls as the original Enigma cipher?

As a more general question, can other older ciphers be "re-invented" for computers and be viable in today's world?

Yes, if you are willing to throw enough resources at it. Only the most fatally flawed schemes cannot be rescued (in practical terms) given enough additional computation. Since you are even willing to enhance the rotor complexity, you could actually use it to implement a modern algorithm exactly. The ability for a rotor to advance "forward a different number each time" makes it sound like quite a programmable architecture.

But why would you want to? (other than it being a cool project of course) What you would end up with would certainly be many times less efficient than a modern cipher running on modern hardware. Additionally, an attacker who was able to develop custom hardware (FPGAs or ASICs) would likely have access to a far more efficient implementation than the defender.


Could a symmetric encrypted communication with a SHA-512 hash still be manipulated? I just got back from an exam review and there was a question I remembered that I apparently got wrong. I wonder if someone could help me with this, since it bothers me.
The question was something like that:
Between a client and server, a symmetric encryption algorithm is used for the communication. The encrypted data is then hashed with SHA-512 and added to the data stream.
Would a man-in-the-middle be able to meddle with the message in a way, the software would not be able to identify the manipulation? It's important that the attacker does not need to get access to the content of the message or manipulate it in a meaningful way. Just the general possibility.
In my answer, I said that, yes, it was possible, but got 0 points on my explanation. I would be interested in the correct answer to that question, out of sheer interest.

Let the message $m$ is encrypted as $c =\operatorname{E}(k,m)$, the hash of ciphertext is $h = \operatorname{H}(c)$, and send as  $(c,h)$ pair. Then the attacker captures the transmission, (possibly stop and send) and

Random ciphertext: change the ciphertext $c$ into any value $c'$ and calculate the hash of it $h' = \operatorname{H}(c')$ and sends. The message will have no meaning at all.

The Replay attack; the attacker sends old messages on their behalf. This is more serious since if not protected, all messages are meaningful. Consider that you send a money transfer message, and it is replayed again and again.

Bit-Flipping attack: If the attackers know the message and for encryption, the CTR or CFB mode of operation is used then they modify the ciphertext bits to their advantage and calculate the hash of the modified ciphertext. This is the strongest assumption, however, can have devastating effects. Like $\texttt{attack at fall}$ can be turned into $\texttt{attack at down}$.

Length extension attack: the attacjer executes a length extension attack on SHA-512 on the hash value $h$. $$h' = \operatorname{SHA512}(c\mathbin\|pad1\mathbin\|extension)$$
Then modifies $c$ as $c' = c \mathbin\|pad1\|extension$ and sends the message pair as $(c',h')$.
The receiver checks the hash of $c'$ and sees that it is a valid hash then decrypt the $c'$ as the intended ciphertext. done!
This length extension attack has almost no cost for the attacker, however, they have no control of the decryption of the appended text.
To make the length extension attack easier the attacker can define a new $\operatorname{SHA-512}$ as $\operatorname{SHA-512x}(IV,m) $. If the $IV$ is equal to initial values of $\operatorname{SHA-512}$ then it is exactly $\operatorname{SHA-512}$, in the other case they can use the $h$ as an $IV$ to execute the attacks as $\operatorname{SHA-512x}(h,extension)$. This will reduce the cost of the extension attack.


AES Algorithm processing time in Arduino vs Raspberry Pi The Arduino employs an 8-bit ATmega series microcontroller whereas the Raspberry Pi is based around a 32-bit ARM processor, and the Arduino is typically clocked at between 8-16MHz and with 2-8kB of RAM available, and in contrast the Raspberry Pi can be clocked at up to 1GHz and may have up to 512MB of RAM.

This clearly states that AES Algorithm will work way too faster on RPi than on Arduino, yet, out of curiosity, what would be the maximum time Arduino would take to perform AES-256 Encryption with the encryption key provided. ?

Is there anyway to calculate these timings for both Raspberry Pi and Arduino ?

In principle, it is theoretically possible to calculate the time it takes a machine to run some known algorithm.
It used to be fairly commonplace, but there are apparently very few people who have ever done it -- the sorts of things that used to require isochronous code are now-a-days generally done in other ways.

In practice, it's generally simpler and takes less human effort to write the code and run it on the target machine and measure the time.
According to people on the Internet, some implementations of AES-256 that run directly on the 16 MHz Arduino can encrypt approximately 1 block per millisecond, roughly 32 000 bytes/sec.
(a) (b) (c) (d) (e) (f)

I hear that AES implementations are available on many other 8-bit processors.
AN953 "Data Encryption Routines for the PIC18" describes two AES implementations for a 10 MHz PIC. The "C" implementation decodes 3 400 bytes/sec; the assembly implementation decodes about 14 000 bytes/sec.
 (g) (h) (j)

I also hear that many people connect Arduinos to some other devices that does the AES encryption for them, such as some ZigBee and XBee radios with the "Enable AES 128 encryption" command.

Have you heard that Carl is doing AES+CTR+HMAC Encryption and Authentication on an Arduino ?


Brute Force on Curve25519 I was thinking about a brute force attack on Curve25519. For this, we need to solve the discrete Logarithm problem $P = [n]Q \bmod 2^{255} - 19$. $P$ and $Q$ are known Points on the elliptic curve, so we 'only' need to find $n$. The $n$ is in $ \{2^{254} + 8 \cdot \{0,1,2,\ldots,2^{251}-1 \} \}$. So there are $2^{251}$ different possibilities for n. On average the brute force attack needs to test $2^{250}$ different n.
We want to calculate how much time the best supercomputer in the world would need. Bernstein says that it needs 640383 cycles for one multiplication. 92% are floating points operations (flop) so i approximated this to 100% flop. The best supercomputer can do $148600 \cdot 10^{12}$ flops. Combining this information, I achieved the following result:
$$\dfrac{2^{250} \cdot 640838}{148600 \cdot 10^{12}} \cdot \dfrac{1}{60\cdot 60\cdot 24\cdot 365.25} \approx 2.47243\cdot 10^{56} \text{ years}$$
Do I have an error in reasoning?

Ok, it answer the specific question you asked:

Bernstein says that it needs 640383 cycles for one multiplication

Actually, when Dan talks about "multiplication", he is referring to a "point multiplication", that is, to the computation of $[n]P$ (given a large integer $n$ and a point $P$).
In your simple-minded brute force search, you don't need to do a full multiplication each time.  Instead, when you have computed $[a]P$ (and decided it is not $Q$), you can step to the next one by computing $[a]P + P = [a+1]P$; this is a point addition (and incrementing the value $a$ you're keeping track of), this is much cheaper than the full point multiplication operation.
Now that is mentioned the obvious misstatement in your analysis, some general advice; to do a reasonably thorough security analysis, you'd need to consider:

The various computational models that an adversary may have available; in addition to a single large computer, the adversary may have a large number of smaller computers, a set of GPUs, a set of FPGAs2 or even (if his budget allows) some ASICs.  Dan used floating point in his implementation, but that's because modern CPUs have some pretty fast floating point logic, and he took advantage - however, there are a lot of gates tied up in this fast floating point logic; some of the other computational models would use different strategies.

The various attacks; in addition to the rather naïve brute force search, you would also need to consider various "square root" attacks (such as Baby Step Giant Step and Pollard Rho (and parallelized versions), and also the MOV (which doesn't apply to Curve25519, however you'd need to learn why).

What Dan wrote is a decent starting point; however he assumes that the reader is already familiar with the basics of elliptic curves; I suspect you'd want to do some reading to catch up...


Adding two RSA private key We've constructed a new private RSA key from two known private RSA keys $Priv_1$ and $Priv_2$ as follows:

$$p = next\underline{}prime\left(\frac{Priv_1(p) + Priv_2(p)}{2}\right)$$

and

$$q = next\underline{}prime\left(\frac{Priv_1(q) + Priv_2(q)}{2}\right)$$

where $Priv_{1}(p)$ is the first factor of $Priv_1$ and so on.

The keysize is 2048 bits. Suppose that we know the three public keys of $Pub_1$, $Pub_2$ and $Pub_3$, that $Pub_3$ corresponding public key for $p$ and $q$. Is it possible to find $p$ and $q$?

Problem re-statement and notations: we know three 2048-bit RSA public moduli $N_1$, $N_2$, $N$, of unknown factorizations $N_1=p_1\cdot q_1$, $N_2=p_2\cdot q_2$, $N=p\cdot q$, with $p_1<q_1$, $p_2<q_2$. We additionally know that $p$ is the smallest prime at least $(p_1+p_2)/2$, and $q$ the smallest prime at least $(q_1+q_2)/2$. Can we use that to help finding $p$ and $q$?

The quantity $N^2/(N_1\cdot N_2)$ reveals something about $p_1$ $p_2$ $q_1$ $q_2$ that we had no way to know without $N$. But there's no reason that this quantity would be strongly revealing of $q_1/p_1$ or $q_2/p_2$.

If we ignore the small increments to the next prime, and the Diophantine aspect of things, we have only 5 equations (ignoring inequalities: $N_1=p_1\cdot q_1$, $N_2=p_2\cdot q_2$, $N=p\cdot q$, $p=(p_1+p_2)/2$, $q=(q_1+q_2)/2$) among 6 unknowns ($p_1$ $q_1$ $p_2$ $q_2$ $p$ $q$), with 4 unknowns randomly seeded in a large interval and the other two also varying in a large interval. Given these, $q/p$ (or $q_1/p_1$, $q_2/p_2$) can still vary widely and can't be closely estimated, which would have enabled a Fermat-like factorization.

Thus as far as I can tell: no, we do not know how to find $p$, $q$ much easier than by factoring one of $N_1$, $N_2$, or $N$.