Nonlinearity of the J-K Flip Flop In Encryption Schemes for Computer Confidentiality, Pless describes how to use the J-K flip flop as a nonlinear combiner for linear feedback shift registers.
This generator was broken because the J-K flip flops are not correlation immune but my question concerns the basic nonlinearity of the J-K function itself: how do you measure its nonlinearity? For instance we know that Boolean functions with maximum nonlinearity are the bent functions, which have the farthest distance to all affine functions. Then we have the linear functions like XOR, so where would the J-K flip flop fit into this spectrum?

There's no way to reduce the J-K flip-flop to a boolean function, much less a 2-input boolean function. The J-K flip-flop is a 3-input block with a clock input in addition to inputs $J$ and $K$. Its output(s) is/are not a boolean function of these inputs, because past output(s) matters to future output(s).

If we want to model a J-K flip-flop using boolean functions, we can do this in several ways, including two identical 3-input functions $Q(I,B,C)=(I\cdot B\cdot C)|\bar B$, where $I$ is $J$ for one function and $K$ for the other, $B$ is the output of the other function, and $C$ is the clock, as per this schematic:

Knowing the initial state $Q$, and the inputs $J$, $K$, $C$, this allows predicting future $Q$, except for some inputs where $C$ changes near-simultaneously with either $J$ or $K$.

The article considers a J-K flip-flop with single output, sharing its clock input (made implicit) with the sources feeding its other two explicit inputs $J$ and $K$. The model given is:

a gated D latch with single output (as used for individual bits in a Linear Feedback Shift Register);
and a (boolean) feedback function, which 3 inputs are $J$, $K$, and the output.

The state (noted $R_n$ in the article) of the output $Q$ of the J-K flip-flop at a certain clock period $n$ is
$$R_{n+1}=((J\oplus \bar K)\cdot R_n)\oplus J$$
(as can be deduced from any proper model of the J-K flip-flop, including the above model as two boolean functions). And thus, in a modern exposition, anything using the J-K flip-flop in this clock configuration can be readily expressed in the framework of Non-Linear Feedback Shift Registers.

In the shared clock configuration of the article, the J-K flip-flop's feedback function given above is a 3-input, 1-output boolean function $F(J,K,R)=((J\oplus \bar K)\cdot R)\oplus J$, where the additional input $R$ is the previous output. The truth table for $F$ can be condensed from the normal $2^3$ entries to
$$\begin{align*}
J&K&F\\
0&0&R&\text{ unchanged}\\
0&1&0&\text{ clear}\\
1&0&1&\text{ set}\\
1&1&\bar R&\text{ toggle}\\
\end{align*}$$

This function $F$ is balanced (that is, half of the $2^3$ outputs are 1), and $F(J,K,R)\oplus R$ is also balanced. $F$ is non-linear w.r.t. each of its inputs (that is, the XOR of the output with any input is not a function of the other inputs).

$F$ is not correlation-immune: the output is biased towards $J$, and towards $\bar K$. This indeed allows an attack in the context of combining LFSRs, but replacing $F$ with any 3-input boolean function can't improve this; enumerating the 256 such functions, we would find some issue with the output (ordered from worst to least):

severely biased (that's why we want $F$ balanced);
severely correlated to the previous output (that's why we want $F(J,K,R)\oplus R$ balanced);
equal within polarity and a clock delay to one of the two inputs, which (being a LFSR) is efficiently predictable using the Berlekampf-Massey algorithm;
equal within polarity and a clock delay to the XOR of the two inputs, which is efficiently predictable by the same method, because the XOR of the outputs of any two LFSRs is identical to the output of another LFSR of size at most equal to the sum of the sizes of the two LFSRs;
just as correlated with the inputs as in the J-K flipflop case.

Note: I'm not familiar with the definition of bent and semi-bent functions, and won't attempt to classify where $F$ belongs, but that should be trivial from the definition of bent and semi-bent, whatever that is.

Note: The J-K flip-flop seems to be one of the simplest two-inputs combiner with memory worth consideration in the framework studied by Frederik Armknecht and Matthias Krause in Algebraic Attacks on Combiners with Memory (Crypto 2003).


What is logical key hierarchy (LKH)? The question "Virtual key generation in Logical Key Hierarchy" asks how specific keys are constructed in LKH. Since I haven't heard of it and it isn't immediately obvious (not even from the linked RFC) what it does or how, can somebody provide a short explanation?

Since I haven't heard of it and it isn't immediately obvious (not even from the linked RFC) what it does or how, can somebody provide a short explanation?

In short, Logical Key Hierarchy – LKH – is a solution to handle keying issue in secure group communication. LKH is interesting because it allows keying in an efficient and scalable way by minimizing the number of transmissions in rekeying as well as storage requirements. (At it's core, there's a binary tree.)

You might want to check the ample materials available online (which you can find using your favorite search engine) for examples. Mentioning only two random materials of many: there's a short, 15 page lecture from 2003 by D.R. Stinson (PDF) and there's Logical Key Hierarchy Protocol (PDF) for a protocol example.


Linear secret-sharing scheme for four players I got stuck on this question during my exam revision.

Consider the linear secret-sharing scheme for four players $P_1, P_2, P_3$ and $P_4$ based on the matrix
$$
M=
  \begin{bmatrix}
    1 & 0 & 0 & 0  \\
    1 & 2 & 3 & 3 \\
    0 & 1 & 5 & 5 \\
    1 & 4 & 3 & 6 \\
    0 & 5 & 2 & 4 \\
  \end{bmatrix}$$
whose entries are elements of $GF(7)$. The dealer shares a secret $s \in GF(7)$ using random elements $r_1, r_2, r_3 \in GF(7)$ by computing $M(s,r_1,r_2,r_3)^T$ and letting the share of player $P_i$ be the $(i+1)^{th}$ coordinate of the resulting 5-tuple.

How do I show that $\{P_1,P_2\}$ and $\{P_3,P_4\}$ are the only pairs of players who can recover the secret?

How do I show that any set of three players can recover the secret?

First, calculate the parity-check matrix $H$, whose rows generate the null space of $M^T$. $H$ is a generator matrix for the dual code $C^\bot$ of the linear code $C := \{ x \, M^T \}$ associated to your secret-sharing scheme. The access structure of your scheme is given by the minimal codewords $\mathbf x = (x_0, x_1, x_2, x_3, x_4)$ of $C^\bot$ that have $x_0 = 1$; specifically, $\{P_i : x_i \neq 0\}$ is a minimal reconstructing set if and only if there is a minimal codeword $\mathbf x$ in $C^\bot$ with $x_0 =
 1$ (Massey, 1993).


Key Refresh in Diffie-Hellman Assume the case, that two participants have agreed on a key $K=g^{ab} \mod p$ via Diffie Hellman. I have the need to change the key every now and then. The first idea I had was to simply initiate a new agreement, so both chose another exponent, so the new key would be $K'=g^{a'b'}\mod p$.

I wonder if it would be also a secure method to just change the generator, so that $K'=h^{ab}\mod p$. Is there something I've overlooked (as I am a newbie to number theory), that would make this a bad approach?

There are a bunch of issues involved with this question; the bottom line is that it while it wouldn't be a bad approach from a cryptographical standpoint, it appears to be more costly than the standard approach.

Let us first examine the number theory issues: the first question to ask is "does $g$ generate a large prime subgroup of $Z/p$?". That is, does $g^x \bmod p$ take on a prime number of distinct values (depending on $x$), and that prime number is fairly large?  If that's not true, you need to change your values of $p$ and $g$ so that it is true.  If you need a suggestion about what group to use, I always point people here; this gives a number of precomputed groups that are well designed.

Now the good news: as long as you're working in a prime subgroup, it doesn't matter which generator you're using; all elements of the subgroup (other than 1) generate the entire subgroup and (here's the best part) none are weaker as far as Diffie-Hellman is concerned.  To be more precise; if someone can solve the computational Diffie-Hellman problem with a generator $h$ (that is, given $h^a$ and $h^b$, compute $h^{ab}$), then he can solve the Diffie-Hellman problem with generator $g$; hence if $h$ is weak, then $g$ turns out to be weak as well.

Now, let us examine another issue: why are you rekeying in the first place?  What security properties do you hope hold for the new keys?  Do you hope to get Perfect Forward Secrecy (PFS, that is, if someone happens to get hold of the entire cryptographical state on one of the two sides at some point, they are still unable to obtain the new keys)?

If you are changing keys simply because that's good cryptographical practice (and don't care about PFS), there are a number of ways to do this securely.  We generally don't bother recomputing a public key operation (which is expensive); instead, what we generally do is use a Key Derivation Function to convert the DH shared secret (and some public nonces exchanged by the two parties) into the actual keying material we use; when we want to change keys, we just rerun the Key Derivation function with different nonces (possibly exchanged that that time); and we have new keys which are cryptographically unrelated to the previous keys.

On the other hand, if we want to get PFS, the recomputing the Key Derivation Function doesn't work (because an attacker with the previous state can do that as well); to do that, we generally do another DH exchange; that gives us PFS because we select new secret exponents at the time of the exchange; someone learning the state previous to that doesn't learn the secret exponents, and hence cannot learn the new keys).

We might consider doing a virtual DH exchange with another generator; the issue is "where does $h$ come from, and do we know the value $x$ such that $h = g^x$?  Note that they may appear to be a Discrete Log problem, however we may know the value $x$ by selecting that first, and then computing $h = g^x$.

If we know such the value $x$, then both sides can compute ${(g^{ab})}^x = h^{ab}$.  However, if both sides can compute it, so can the attacker (who learns the previous cryptographical state), and so you don't achieve PFS.  If you don't need PFS, this works, however rerunning a Key Derivation Function is rather cheaper than doing another modular exponentiation.

If we don't know such a value $x$, then both sides would need to compute $h^a$, $h^b$ and exchange them; effectively doing another Diffie-Hellman operation.  However, in contrast to an independent Diffie-Hellman operation, both sides must retain their $a$, $b$ values; and so an attacker learning the cryptographical state would learn one of those values, and so you don't achieve PFS.  Now, you could have the two sides discard their $a$, $b$ values, and select new ones; at this point, you're doing the traditional Diffie-Hellman, except you're changing generators; that isn't harmful, but doesn't appear to gain you any benefits either.

So, the bottom line is that if you need Perfect Forward Secrecy, your proposal doesn't do it; if you don't need Perfect Forward Secrecy, there are cheaper ways to do it.


Why does Skein use an output transform, but other similar hashes don't? Skein uses an additional compression function call to finalize the output, even when the output isn't larger than the native output size.

The Skein paper says:

  Due to Skein’s output transformation, it remains an open problem how to create collisions or second preimages for the Skein hash function, even if one can create pseudo-collisions or pseudo-second-preimages for the compression function.

and

  Output transformation. Originally we applied the output transformation only if the output size
  was larger than the state size. Unfortunately, without the output transform, you can construct two messages $M$ and $M'$ such that $H(M) ⊕ H(M')$ is the same as the XOR of the last blocks of $M$ and $M'$. (A similar property has recently been described for SHA-1 [101].) This violates the requirement that the hash function behave like a random mapping.

At a high level Blake has a very similar construction but doesn't use such an expensive finalization. Is there a technical reason why Skein needs such a finalization, but Blake doesn't? In particular does the non randomness issue that Skein prevents with the output transform exist in Blake? Why (not)? Is it related to the way Skein turns a blockcipher into a compression function?

The main reason for designing a cryptographic hash function using an
output transformation is flexibility. In the following, I try to
motivate the need for an output transformation.

For example, SHA-256 has no output transformation and a fixed
output size of 256-bit. What happens if you truncate a SHA-256 hash
value? In this case, there are no security claims at all. If something
goes wrong it is YOUR fault, since you have used SHA-256 in an
unspecified mode.

However, the designers of Skein claim the following levels of security
against standard attacks: preimage $2^m$, collision resistance
$2^{m/2}$, where m is the minimum of state and output size.  It is
safe to claim this, as long as the compression and output
transformation are secure. It is hard to claim such a level of
security without an output transformation.

Another problem is the full domain hash (FDH). Assume you are using an
FDH based on RSA-2048. You want to sign messages of arbitrary
length. For the sake of performance, you first have to hash and then
sign the hash values. If your hash value is smaller then 2048-bit you
need a secure padding.  To avoid this, Skein allows to invoke the
output transformation multiple times. In our case you will
call the output transformation -- over and over again -- until you have
an 2048-bit hash value.


Weil pairing of P and Q it the following example for page 56 of the book http://www.craigcostello.com.au/pairings/PairingsForBeginners.pdf I could not understand how the author found the Weil pairing of two points p and Q. I attached the picture of the example. Can you help me to this? Thanks.

They used Miller's algorithm, which is explained in the next chapter.

(To be concrete, they used a implementation in Magma which is available in the author's website)


Why equation Y^2=X^3 +AX+B can't work with finte field of charateristic 2? I know that we can't define $dx/dy$ with this equation because $2y = 0$ with finite field of charateristic $2$. But with $GF(2^n)$ (has characteristic by $2$) $2=x$ not $0$. Do I misunderstand here?

In $GF(2^n)$, $y+y = 0$ for all $y$. These elements are not integers; using something like “2” to denote a field element is merely a convention, and, as you demonstrate, a confusing one. In this case, $2y$ means $y+y$, not the product in the field of $y$ with the element conventionally represented by “2”.


Are there benefits for using Static Diffie-Hellman over Ephemeral Diffie-Hellman? TL;DR - Are there any benefits to using static DH over ephemeral DH?

I'm reading about the differences between static DH & ephemeral DH  and I am trying to think of one logical reason to use static(-static) DH over ephemeral(-ephemeral) DH.

My understanding of DHE is that it provides Forward Secrecy which is something we want, is it not? FS ensures that if the server private key were to get leaked past communication would be secure correct?

So why would we still want to use static DH? Are there any benefits to this? I would presume that computation is perhaps one factor?

The "advantage" of static DH is that the server doesn't need to compute an exponentiation each time. This advantage is, however, not worth it, in the sense that the static DH problem is easier than the DLOG problem (to the best of our knowledge). In the paper The Static Diffie-Hellman Problem (PS) by Brown and Gallant, they show an attack on the static DH problem for Elliptic curves that is significantly faster than the best known for ephemeral DH.

Note: I would not call static DH "standard"; on the contrary, in my mind, ephemeral is the "standard" version.


How long to reestablish PKI if Diffie Hellman and Factoring are in classical $P$? Supposing there is a classical (no need quantum) $O(\log N)$ algorithm to factor integers $N$ and supposing there is a classical (no need quantum) $O(\log p)$ algorithm to find $g^{xy}$ given $g^x$ and $g^y$ over cyclic groups of cardinality $O(p)$ (which includes elliptic curve cryptography) where the constants in $O(\log N)$ and $O(\log p)$ are very small then current $PKI$ breaks apart.

What alternatives are there to reboot the internet with a new public key infrastructure and how long would such an effort take?

I would think certain post quantum cryptosystems will also be deemed useless.

Note I am not assuming Discrete Logarithm is broken and since equivalence between Diffie Hellman and Discrete Logarithm Problem is still open I believe we will have something similar to PQC situation but not identical.

Can we have a full-fledged PKI with just a strong signature scheme when factoring and all varieties of DH are broken?

Of course we can; we have a number of signature algorithms that do not rely on either factoring or DH (or Discrete Log, for that matter)

how long would such an effort take?

That's the hard question; while efforts are currently underway (because of the possibility of Quantum Computers, which would be able to solve all the problems you have listed), it's not expected to fully replace RSA or E*DSA[1] for perhaps 10-20 years (10 years would be when the large majority of PKI would be "postquantum"; 20 years would be the time it'd likely take to convince every obscure webserver to convert).
In your scenario, all this would need to be drastically sped up.  The time that'd take would have to be an estimate; there are the problems that'd need to be solved (and I'll focus in on the PKI piece; there are other pieces, such as key exchange, uses of signatures disconnected from the global PKI, and more advanced crypto, such as IBE and PAKE, that would also need to be addressed).

We'd need to select a signature algorithm; such an effort is currently underway, however we're hoping to have two or three more years to gather information to allow us to make an informed choice; in your scenario, we can't wait that long.  I'm guessing the community would pick one (likely either Falcon or Dilithium) in a month or two - those two are the most likely, because testing has shown that neither would slow down TLS significantly, and the best evidence we have now show them likely to be secure (and we're hoping to firm up that last statement in the next few years).

The various PKI vendors would need to issue new root public keys using this new method (and distribute them).  How long this would take is more a question about internal company politics more than practicalities; some CA vendors will jump on the ball immediately; others (based on my conversations I've had with them over the years) are more likely to ignore the problem until forced to by customer demand.

Various browsers (and software libraries, such as OpenSSL) would need to incorporate these new methods and root public keys (and somehow deal with older websites that haven't updated yet).  From my experience, all the major browser vendors are likely to be fairly quick about this.  On the other hand, other clients (which might not be presented as browsers to the user) might be considerably slower to update.

Various websites would need to have new certificates issued to them, and to use the new signature method.  That's a long pole - the major websites (Google, Amazon) and website hosting services (CloudFlare) are likely to be quick about this.  On the other hand, there is a large number of smaller, not that well maintained servers that will be quite reluctant to upgrade (even if they are still being actively maintained).

Going through this list, my guess is that a significant amount of the web traffic would likely to be protected by an upgraded PKI in perhaps 6 months (of fairly intensive work by the community); however there will be some traffic that won't be for years...
[1]: E*DSA is my personal terminology for the collection ECDSA, EdDSA, Schnorr signatures and similar schemes.


Can POS devices really generate random numbers? I am doing an implementation of a system designed by a payment company and I am a little skeptical about the way they have designed the end to end cryptography.

The system is as follows:

There are three parties in the data exchange

Sending party (A)
Switching party (B)
Receiving party (C)

Party (A) is a POS device having a very little computing power.
Party (B) is the payment company
Party (C) is an authorizing institution

On the POS device, biometric data is captured and POS device have a public key of (B). The POS device will generate a random 128-bit key and encrypt data using this key and then again encrypt the entire dataset with public key of (B) and send it to (B).

Party (B) also maintains symmetric keys for party (A) and (C). Once it has data from party (A) it decrypts it and then encrypts the data set using symmetric key of party (c) and sends it.

Party (C) will use its key to decrypt the data first and then uses 128-bit key received from dataset to decrypt the remaining data.

My concerns on this methodology is: Can POS devices really generate a random number?

Modern POS devices are designed to meet the strict security requirements of payments industry (search for PCI-DSS standards). They are typically based on a SoC designed specifically for secure payment applications. An example of such SoC:
https://www.broadcom.com/products/embedded-and-networking-processors/secure/bcm5892/#overview

From the datasheet:
"The random number generator (RNG) is a true random source. It utilizes free-running oscillators to capture thermal noise as the source of randomness. It has been used in numerous devices (such as BCM5820, BCM5821, BCM5841, or BCM5890) and been evaluated as a valid source for seeding FIPS approved pseudo-random number generators as the initial secret value"

If the POS in question runs Linux - it's fairly new, but if in doubt you can always query its vendor directly.


Security impact of signing small data using RSA I have an application which consists of a client and a server. Both have a pair of public and private key (RSA). For communication, both sign their messages and send them to the other part. So a message Looks like this:

_____________________
| HTTP Post request |
|___________________|
|     Post data     |
|___________________|
|     Signature     |
|___________________|

The post data is signed with the private key and the signature is added to the data. Sometimes the post data is very small (sometimes it just contains one number).

I know it can impact performance very much if I sign every little piece of data, but this time I'm not concerned too much about performance as the frequency of signing is very low.

Can it cause security problems if I sign very small amount of data such as just one number?

If you are using a secure signature algorithm, padding and all, then it must be secure for messages of any length. So in that sense you are good.

However, in many protocols your messages must include something to prevent replay attacks, like an incrementing counter, in which case you shouldn't be signing just a single number if the messages are meant to say anything at all.


Why is ECDSA secure? I'm trying to understand why is this, in my opinion, counter intuitive construction secure. ECDSA is a tuple of two numbers (r, s) whose validity can be verified by public key. However I don't see the reason why the only way to forge the signature is breaking the DLog problem on the EC. I spent many hours thinking about it and still don't comprehend where is the bottleneck. How do we know that there is no other algorithm for generating (r, s) without the knowledge of private key?

We don't. As far as I know there is no proof of security for ECDSA in any model. There is, however, almost 2 decades of usage in the wild, including by Bitcoin and Ethereum, which would allow any would-be attacker to make a tremendous amount of profit. The fact that this appears to have never happened is good empirical evidence for its security.

I've also spent a while exploring this problem. I believe that if you model the mapping from a curvepoint to its x-coordinate as a random oracle function you can use a forking lemma argument to prove the signature secure. This is unrealistic but it implies that any forger would need to find a meaningful relationship between points and their x-coordinates, and it's hard to imagine such a thing that wouldn't also solve the discrete log problem.


efficient authentication with broadcast encryption? (I am not a crypto expert, so I apologize if the terminology I use is incorrect.)

Suppose I have the following simple broadcast encryption scheme for securely sending content to $n$ authorized recipients using only symmetric-key algorithms:

each authorized recipient is given a recipient key (known only to the sender and recipient)
the sender generates a random key to encrypt a message (content key)
for each receipient, the sender broadcasts the content key encrypted with the recipient key
each recipient uses its recipient key to decrypt the content key
the sender broadcasts the message encrypted with the content key
each recipient uses the content key to decrypt the message

With the above scheme, there is no authentication.  A man-in-the-middle attack would allow one recipient to undetectably alter the original message on its way to another recipient.  Some additional steps could fix this:

the sender calculates a cryptographic hash of the content
for each recipient, the sender broadcasts the hash encrypted with the recipient key
each recipient decrypts the hash and uses it to authenticate the message

My question:  Is there a scheme that allows recipients to authenticate the message without the $\operatorname{O}\left(n\right)$ overhead of sending the encrypted hash and without using asymmetric cryptography?  If not, can the overhead be reduced?

The answer to your question is yes this is possible, but if we don't use assymetric cryptography, we need an alternate source of assymetry. One option is using time-delayed schemes. In such schemes, the key for the MAC is not initially disclosed, but only after some time interval.

See here for TESLA that accomplishes this. TESLA has a drawback in that it requires an initial digital signature to send the initial parameters. A second variation of TESLA, uTESLA  achieves this without digital signatures.


Using a Non-Random IV with modes other than CBC The weakness CWE-329 is an interesting problem with CBC mode.  However, does this same weakness affect the other modes of operation that rely upon an IV such as: PCBC, CFB and OFB?  My gut feeling is, YES.  I am wondering if there a consensus on this topic?  Or is there a possible explanation of why its not a weakness.

Each mode of operation has its own IV requirements. Some need uniform, unpredictable randomness. Other are equally happy with just uniqueness.

CBC is well-known for its need of an IV chosen randomly and uniformly among the possible IV values, and such that an attacker who can choose the text to encrypt may not predict the IV value before submitting the said text.

PCBC is similar to CBC in that respect. When encrypting, PCBC is equivalent to applying a linear transformation on the input data, followed by CBC encryption. So PCBC also needs a uniform unpredictable IV.

CFB and OFB require only uniqueness: for a given key, each IV value shall be used at most once. The is no need for unpredictability or uniformness because the IV is first encrypted "as is" (before any operation with the plaintext) and encryption of a sequence of values with a good block cipher, using a key that the attacker does not know, is a good PRNG. This means that CFB and OFB somehow include what it takes to elevate a unique IV to appropriate uniform randomness.

CTR is somewhat similar to OFB. CTR encrypts the successive values of a counter, and the IV is the initial value for the counter. Security is achieved as long as no counter value is ever used twice with the same key. Hence, using CTR "burns" a range of consecutive values, beginning with the IV; none of these values shall be used afterwards as IV.

Note that OFB also generates a pseudo-random stream, and using as IV one of the block cipher outputs in a previously generated stream means that you regenerate the same stream from that point. So OFB also "burns" a bunch of values. However, these values are uniformly distributed in the set of block values, and not numerically consecutive as with CTR. The consequence is that a +1 policy on IV management (you emit several messages, each encrypted separately but with the same key, and simply increment an internal counter to get the next IV) is acceptable for OFB mode -- but not acceptable at all with CTR.

Remember the bit about CFB and OFB including their own PRNG ? The idea has been reused. Many modern block cipher modes, especially those which include checked integrity such as EAX or GCM, do the same kind of trick, and only require uniqueness.

Uniqueness and randomness are two distinct properties. Randomness is hard to get in some context; most desktop machines and servers manage to maintain an acceptable source of randomness (/dev/urandom, CryptGenRandom()... the name depends on the OS), but many embedded systems cannot. On the other hand, uniqueness is not totally free either: it needs some kind of memory, which resists across reboots. Using the current time as IV is tempting but delicate, unless you can guarantee a monotonous clock (otherwise, an attacker could reset the clock to trigger IV reuse).

However, appropriate cryptographically strong randomness yields uniqueness "for free" with overwhelming probability (if the block size is large enough, but you want to use 128-bit blocks for other reasons anyway). Therefore, if you have a strong PRNG on hand, you can use it to produce your IV for all modes.


AES: Changing plaintext to state Can someone explain this to me?
For example how M chanes to 0c?

Changing plaintext to state:

This question has nothing to do with AES; instead, it has to do with an encoding that someone picked for this example (and the fact that you have questions about it indicates that it wasn't a great choice by whoever came up with the example).

The encoding is simple; we translate the letters 'A' through 'Z' to the integers 0 to 25, which is in hexidecimal the values 00 through 1A.

M is the 12th letter after A, and hence it is translated into the integer 12, which is 0C in hex.


Get $a$ such that quadratic residue has a solution (Rabin) My task is to implement Rabin signature. I have trouble with choosing padding a such that
$$x^2 \equiv a \pmod n$$
has a solution.

In that context, $n=p\cdot q$ is composite, where $p$ and $q$ are prime numbers with $p\equiv3\pmod 4$ and $q\equiv3\pmod 4$.

How do I check if a solution exists?
Is there any formal way to find $a$?

The equation $a = x^2 \bmod N$ has at most $4$ solutions $x$.

There are solutions if $a$ is a square modulo both $p$ and $q$.  This can be checked by computing the Legendre of symbol of $x$ modulo $p$ and modulo $q$.

Assuming that the two Legendre symbols are +1, when $p \equiv 3 \pmod 4$, a square-root of $a$ modulo $p$ is given by $x_p = a^{(p+1)/4} \bmod p$; the other square-root modulo $p$ is given by $-x_p$; and simililarly modulo $q$.  The square-roots modulo $N$ are then obtained through Chinese remaindering (CRT): $x_1 = \mathrm{CRT}(x_p,x_q)$, $x_2 = \mathrm{CRT}(-x_p,x_q)$, $x_3 = \mathrm{CRT}(x_p,-x_q)$, $x_4 = \mathrm{CRT}(-x_p,-x_q)$.

For example, suppose $p = 852151$ and $q = 376963$ (note that $p,q \equiv 3 \pmod 4$).  And so $N = pq = 321229397413$.  Let also $a = 187078154864$.  It is verified that the Legendre symbol of $a$ modulo $p$ is $+1$, and similarly modulo $q$.

From the previous formula, we obtain $x_p = 295070$ and $x_q = 21456$.  The four square roots of $a$ are then obtained through Chinese remaindering: $184209776740$, $156318284370$, $164911113043$, and $137019620673$.

Remark 1:  The Legendre symbol of $a$ modulo $p$ is given by $a^{(p-1)/2} \bmod p$.

Remark 2:  Given $x_p$ and $x_q$, $\mathrm{CRT}(x_p,x_q) = x_p + p[i_p(x_q - x_p)\bmod q]$ with $i_p = p^{q-2} \bmod q$.


Starting stream cypher, first block (Salsa20) I'm implementing Salsa20 in Rust for fun.

I have the initial state (4x4 32-bit matrix) setup from the key, nonce, and stream position 0. I'm using the Wikipedia Salsa20 article as reference, and I'm confused on how to encrypt the first block. QR is applied on the 4x4 matrix, but how do I "mix in" the input? Is there a better reference for this algorithm (or stream ciphers in general) I could use to understand the implementation?

I suggest you take a look at the spec of Salsa20. It is quite short and easy to understand. You even have some examples for each component of the implementation.

For more details, you can take a look at this post which explains how to handle different key size (how to treat your initial block, and feed it to the Salsa hash function).


Security of HOTP over an unencrypted channel for controling an actuator I have a simple on/off actuator that I want to control remotely. I want to use available hardware: a pair of microcontrollers connected to a pair of wireless transceiver modules.

Can HOTP algorithm be used over an unencrypted channel securely?

Can HOTP algorithm be used over an unencrypted channel securely?

Yes.

Essentially, HOTP is a stateful function that keeps an internal counter and then computes an HMAC over that counter followed by some truncations to get the right format. In the process the counter is also incremented.

So assuming we can model HMAC as a PRF then the output of each HOTP query is freshly random and unrelated because that's what a random function would do with distinct inputs (and that's how HMAC behaves because it's a PRF). This in particular means that an adversary cannot predict anything about future HMAC outputs or about past unseen outputs.

Of course the only guarantee you get from this is that an adversary cannot predict new authentication tokens and that new tokens likely won't be valid ever again. In particular HOTP by itself does not protect you from things like relay attacks or attacks where the adversary buffers a token and sends it later at a more convenient time.


Verbatim of early work on public-key cryptography? In late 1997, the history of public-key cryptography was turned around with the announcement (then extended) that

public-key cryptography was theorized in a 1970 note [1] by James Henry Ellis: The Possibility of Secure Non-Secret Digital Encryption;
a feasible realization of that, similar to RSA, was described in a 1973 note [2] by Clifford Christopher Cocks: A note on Non-Secret Encryption;
another feasible realization, similar to Diffie-Hellman key exchange, was described in a 1974 note [3] by Malcolm John Williamson: Non-Secret Encryption Using a Finite Field, and a 1976 note [4] (same author): Thoughts on cheaper Non Secret Encryption.

An account of these discoveries is given in a 1987 note [5] by J. H. Ellis: The History of Non-Secret Encryption; this is my rendering of an April 1998 ps archive, and is very similar to this document obtained from the NSA by FoIA case #19136 (narrative).
This calendar of event is confirmed by the December 1977 document [6] by J. H. Ellis: The Authentication Problem, obtained (with references redacted) in the same FoIA case, containing:

Non-Secret Encryption has now reached the phase where it is being considered for possible applications, and I find that many people are worried that the danger of spoofing may make its use untenable.

There is a writing by Simon Singh (in the The Code Book) about J. H. Ellis, C. C. Cocks, M. J. Williamson, and the coming out of the story.

All versions of documents [1]..[5] that I could locate (in 2014) are clearly re-typesettings (with the possible exception of the FoIA source for [5]). Ross Anderson hypothetized that there might have been alterations in the declassification process as an attempt to deny the existence of the then-secret GCHQ by re-attributing the documents to the CESG.
Also, I observe a discrepancy between an indication about [2] given in [3] by M. J. Williamson:

The information rate of the system is low in that 3 bits are broadcast for every 1 of the message. (The ratio in the method of [2] is 2 for 1).

and [2] as we read it, where there is nothing suggesting a significant expansion of plaintext to ciphertext; which in modern terminology is per textbook RSA, with public exponent equal to the modulus, and splitting of message in ECB mode:

The sender has a message, consisting of numbers $C_1$, $C_2$, $\dots$ $C_r$ with $0 < C_i < N$
He sends each, encoded as $D_i$ where $D_i = C_i^N$ reduced modulo $N$.

This opens a possibility that the author of [3] had access to material about [2] different from what we have (perhaps, more extensive than the remarkably terse version that we know). For example it could be that M. J. Williamson considered a single $C$, and the overhead related to $N$, as would be natural if $C$ was the key to another cryptosystem.
Are there public verbatim copies of any of the originals, or hope to obtain these?
Also: Is there an account of the circumstances of the early diffusion of any of these documents?

My wishes largely came true! The GCHQ (briefly) published scans of [1] and [2], and another 1970 document:

[1s]: James Ellis: The Possibility of Secure Non-Secret Digital Encryption
[1.5s]: James Ellis: The Possibility of Secure Non-Secret Analogue Encryption.
[2s]: Clifford Cocks: A Note on 'Non-secret Encryption'.

These scans are excellent, including [2s] which seems to be from a printout of an earlier scan (as visible on an apocryphal annotation on bottom of the second page). The typeset versions of [4] and [1] are very close to [1s] and [2s]; differences are in formatting, typography, and a few transcription typos, like [4] randomly uses MI or M1 where [1s] consistently uses M1.
[1.5s] studies an analog communication over metallic wires trying to resist eavesdropping. It is readily admitted the system is insecure. As apparent to an electronic engineer (even of the 1970s), if an eavesdropper is able to measure both voltage and current on the wire, s/he can break the system.
All in all: it is nice to have these verbatim, but I found nothing that was not essentially known before on the history of public-key cryptography as we know it.


How should I implement a secure recovery of encryption? I want to create a system to host as securely as possible encrypted data in a way that not even the system can know the content of the data, but that it could be recovered.

I would like to know how is it that other systems implement the use of a multiword recovery passphrase, like some bitcoin wallets for example, where the user defines its password, but also gets a set of words to be written and saved securely in case the password is forgotten.

Is this an additional key so that they are 2 possible keys to decrypt the data? or just another form of the same key? What algorithms support this?

I would appreciate any hint or link so I can research deeper.

Thanks

Usually, you have one important key (the master key).
This can be your private bitcoin key, your password database key, the drive encryption key, or really whatever.
Normally you encrypt this key, because you want to change it as infrequently as possible and encrypt it using some user input (e.g. a password) because of costly re-setups of the system.

You now have two ways to implement backups (easily):

Give the user the key and tell them to store it properly (probably ends bad)
Give the user another means of authentication (e.g. a password) and store a copy of the master key that is protected using this mean next to your standard encrypted key.

Method 1:
The advantage of the first way is that it probably is a full backup of the header and thus you can still recover data if the header is corrupted.
The disadvantage of course is that you have to trust the user to store extremely sensitive data of course and this data usually is highly unfriendly to humans, being a random chunk of bytes.
The usual solution to this is to follow the second approach and let the user do backups of the header.

Method 2:
This way you store two copies of your encrypted master key: One for normal operation and one for the backup case. The backup material then allows for access to the data via this encrypted backup copy of the key. Usually you'd also do a backup of the entire header containing this key to prevent data loss.

Finally there's one last method, which is much more difficult to use and may make securing a system very difficult: deterministic key generation. This way you generate your master key in a deterministic way using a password and the same password input will always yield the same key. The advantage being of course that header backups are not really required and that all it takes is a single password. The disadvantage is of course that if the user choses a bad password (if this is an option) that brute-forcing the key via this method probably is a viable attack vector.


UNIX password scheme and encryption function Recent versions of Unix store encrypted passwords in a file that is not publicly accessible. Such files are called shadow password files.

In the UNIX password scheme, if only the operating system and system administrators have access to the password file. What are the security requirements for the underlying encryption function Ek?

Most people would not call what we do to store passwords encryption as it is not reversible. It's a cryptographic hash.

Also the diagram has some specific numbers which correspond to the orignal unix DES based system which nobody should be using any more for many reasons but mainly only 8 chars ASCII passwords. The principals however remain the same.

We want to protext the system also in the event of data from the shadow file is leaked ans to a limited extent from the system adminstrator. It should be impossible to recover the plain text password from what we store, anyone trying to brute force the passwords should need to this one password at a time and not all together. Brute forcing passwords should be a slow process.  It should not be practical to precompute rainbow tables for even a faily modest collection of passwords. We should still be able to verify a given plain text matches the stored record and it should be extremely unlikely another password will accidentally match.

We do this with a special kind of cryptographic hash function and with the help a random salt. The salt (originally  12 bits nowadays more) makes attaxking passwords together and building rainbow tables very difficult. And the hash function should be slow so a single password brute force is impractical.

Since the original implementation we also add that speed should be paramaterized so we can increase compute difficulty as computers become faster. This was missing in the original unix implementation.

Also we want to support long passwords and we want the hash function to preserve as much of the entropy in the password as possible (unlike the infamous LanMan). The hash function should be preimage and collision resistant (unlike the LanMan). Some may want to add diverse charset support which many now use to increase password entropy.


Finding a key given partial keys I'm working through an exam paper for a cryptography exam and I've come across a question I'm unsure on.

Six users have been given the partial keys below

$P(x) = (k + \sum_{i=1}^2 c_ix^i)\bmod{503}$

User X Y

1   10 25
2   20 405
3   30 272
4   40 129
5   50 479
6   60 316

Reconstruct the secret key K to verify it is 138.

I've tried using Newtons Divided Difference to skip using the formula but that didn't work. I also tried using the Chinese Remainder Theorem on the data but that did not work either. I've tried filling into the equation but I don't think I've been doing it right so any help on how to go about this question would be appreciated

Apart from the slightly unusual nomenclature, this is Shamir's secret-sharing scheme with $n=6$ and $k=3$ (i.e., the secret is shared into six pieces, any three of which can be combined to retrieve the secret).

In this case, the pieces are as follows:

$$\begin{align}(x_0, y_0) &= (10, 25) \\
(x_1, y_1) &= (20, 405) \\
(x_2, y_2) &= (30, 272) \\
(x_3, y_3) &= (40, 129) \\
(x_4, y_4) &= (50, 479) \\
(x_5, y_5) &= (60, 316)\end{align}$$

Only three of these are needed to retrieve the secret. As described in the Wikipedia article, this is done by calculating a set of Lagrange basis polynomials:

$$\begin{align}\ell_0 &= \frac{x - x_1}{x_0 - x_1} \cdot \frac{x - x_2}{x_0 - x_2} = \frac{x - 20}{10 - 20} \cdot \frac{x - 30}{10 - 30} = \frac{x^2}{200} - \frac{x}{4} + 3 \\
\ell_1 &= \frac{x - x_0}{x_1 - x_0} \cdot \frac{x - x_2}{x_1 - x_2} = \frac{x - 10}{20 - 10} \cdot \frac{x - 30}{20 - 30} = \frac{-x^2}{100} + \frac{2x}{5} - 3 \\
\ell_2 &= \frac{x - x_0}{x_2 - x_0} \cdot \frac{x - x_1}{x_2 - x_1} = \frac{x - 10}{30 - 10} \cdot \frac{x - 20}{30 - 20} = \frac{x^2}{200} - \frac{3x}{20} + 1
\end{align}$$

All you need from these polynomials are the constant terms, which are multiplied by the corresponding $y$ terms to give you the secret value:

$$\begin{align}s &= (3 \cdot 25 - 3 \cdot 405 + 1 \cdot 272) \pmod{503} \\
&= 138 \end{align}$$


Any use for now-defunct Mt Gox Yubikey? As everyone is now aware, Mt Gox has declared bankruptcy. As what appears to be the very last thing they did, Mt Gox accepted my $35 and fulfilled my special Mt Gox Yubikey. Having just arrived in the mail, I can now rest assured that my Mt Gox account, if it still existed, and all those bitcoins, if they weren't already stolen, would be safe and sound!

Unlike regular Yubikeys, Mt Gox ones are specially hardened. They are write-only and protected by a secret 48-bit access code (known only to Mt Gox). So, outside of making an interesting keychain, or framing it as a constant reminder to watch where I put my money, does anyone know of any interesting things I can do with the Yubikey? Reprogramming, because of the access code, seems to be out of the question, but maybe I can use it for some sort of cool non-cryptographically-secure authentication token?

The access codes were recently leaked (by whom, I don't know).  My Yubikey is listed and I can confirm that the access codes were necessary and sufficient to reprogram it.  You can change or remove the access code as part of reprogramming too.  The leak doesn't make the Yubikeys useless in the extremely unlikely event of Gox rising from the flames — no AES keys were leaked, only the reprogramming ("access") codes — but the AES keys are write-only, so consider whether you care about that unlikely event before doing anything you can't undo.

So go grab the tools, reprogram, and rescue your Yubikey from the TiVo Graveyard.  I think I'll be using mine in static mode only, with one slot unlocking my password manager and the other unlocking an encrypted partition on a headless machine at boot.  If you do something similar, don't forget that (unless similarly headless) you can type a prefix (something-you-know) before hitting the button on the key (something-you-have).


Can anyone explain to me the difference between the OTP (one-time pad) and Vernam Cipher? I heard they are very similar, although there are subtle differences between the two.

Confusion arises because many people use the terms Vernam cipher and one-time pad interchangeably--but they are not the same thing.
When young Gilbert Vernam, an AT&T research engineer, got his patent in 1919 (for a "Secret Signaling System"), Vernam cipher meant a fast encryption method using an additive stream cipher that was machine-based and used Baudet with modulo 2 addition.
XOR was born.
According to this unclassified NSA historical account (p.2):

Gilbert S.Vernam, working on new developments in telegraphy, came up
with a novel (and relatively simple) scheme for encrypting TTY. He
mixed  two  Baudot-coded  punched  paper  tapes (hole  being  a  “+,”
no  hole  a  “-”): one  tape  contained  the plaintext message and the
other the “key.” These tapes were added  “modulo  2”  (“exclusive
or”)  in  a  mechanical  tape reader producing an output cipher signal.

This was a huge improvement over the tedious codebooks and the German ADFGVX cipher, which was susceptible to cryptanalysis. Interestingly, in 1918, the U.S. Army was uninterested in Vernam's work.
But there were several problems no one understood at the time:
1.  The key had not been generated in a truly random manner
2.  The key was on a looped tape
3.  The key was reused

Not a one-time pad.
Enter Joseph Oswald Mauborgne--artist, cryptographer, and U.S. Army General-- the first person to send a radio signal from an aircraft to the ground.  He had the realization that if the key had been generated in a random manner, then the ciphertext from Vernam's machine would be unbreakable.
Frank Miller, an American cryptographer, had already invented the one-time pad in 1882, but the glory seems to have landed on Gilbert Vernam instead of the two people who had actually figured it out.  This reminds one of how Blaise de Vigenère had a cipher named after him that Giovan Battista Bellaso had invented much earlier.
Vernam cipher and the OTP are not the same thing.  Moreover, when we say OTP that can refer to a physical object, usually one that is easy to hide and destroy.
These days, we mostly think of the OTP as a model for encryption systems.


Is there a symmetric-key cryptography based on key establishment techniques? Most of the current key exchange techniques are based on public-key cryptography. Are there any key exchange/establishment techniques based on symmetric-key cryptography too?

In my setup primary assumption is both communicating parties can have pre-shared key  and further they need to exchange messages to derive a longer key for secure communication. (Quantum key distribution is not option for me.)

Are there any practical implementations for the above?

Yes, these are key derivation functions basically deriving a shared secret from information identifying the two parties (like their respective MAC addresses) and nonces and other session communication relevant information. See e.g. the PBKDF2 derivation function.


Question on MAC Forgery In MAC forgery, is it assumed that the attacker has the secret key or not?
I find this in Wikipedia but still not clear.

  Existential forgery is the creation (by an adversary) of at least one message/signature pair, ( m , σ ), where σ was not produced by the legitimate signer. The adversary need not have any control over m, m need not have any particular meaning; the message content is irrelevant — as long as the pair, ( m , σ ), is valid, the adversary has succeeded in constructing an existential forgery.

The key part of the entry is "...where σ was not produced by the legitimate signer.". The legitimate signer is the key holder. We assume the adversary does not possess the key, but would like to have a way to produce MAC tags anyways.


Which answer is true regarding birthday attack on digital signatures? The actual question is:

A sender $S$ sends a message $m$ to receiver $R$, which is digitally
signed by $S$ with its private key. In this scenario, one or more of
the following security violations can take place.
(I) $S$ can launch a birthday attack to replace mm with a fraudulent
message.
(II) A third party attacker can launch a birthday attack to replace
$m$ with a fraudulent message.
(III) $R$ can launch a birthday attack to replace $m$ with a
fraudulent message.
Which of the following are possible security violations?
A. (I) and (II) only
B. (I) only
C. (II) only
D. (II) and (III) only

so if a sender sends a message m to reciever.. I know that an attacker can perform a  birthday attack and send fraudulent message to receiver
But these statements confuse me!

Sender can perform birthday attack and send fraudulent message to Receiver

Receiver can perform birthday attack and create fraudulent message.

I searched upon this but this is too confusing can someone explain? They both seem to be true but the answer i saw states only one is? Can someone explain birthday attack! Thanks

A birthday attacks generates a pair of colliding messages $m, m'$. Because of the way the collision is generated, you can't predict either $m$ or $m'$. If $m$ is fixed, then you need to perform a second-preimage attack instead.

The only person in this scenario who can change $m$ is $S$. $R$ and the third party only receive a fixed message $m$, and have to generate a second preimage $m'$. This is not possible using a birthday attack.

Thus, the correct answer is B. (I) only.


Generate hash value using public key along with message I was trying to understand one way signature chaining on message by Saxena and Soh. As the message is passed from one user to other, every user can combine their signature to create one single signature for a message m. This aggregated signature when passed along with public key of all users who have signed the message can be used to prove that message has been seen by every user.

The chain signature protocol defined under it has 3 steps:

What i do not understand is that in "Chainsign" step, how for a message m, we get different hash values H(i) for different values of L(i). I know that Hash function only takes message as input to yield hash value. How is sequence of public keys Y1,Y2,Y3....Yi is fed along with 'm' to get different hash values? can we practically add key along with message to hash function to get new digest, if so how this mapping is happening?

Actually, the notation of the authors is not complete. They simply do not define what it means to hash several values at once. However, what one would do in practice is appending everything. So $H_i$ would be
$$H_i = \mathcal{H}(m\|Y_1\|Y_2\|\ldots\|Y_i)$$

where $\|$ denotes string concatenation.


Enigma rotation example According to wikipedia: BDZGO is the expected outcome when doing the enigma chipher on the letters AAAAA with rotors I,II,III and reflector B.

ABCDEFGHIJKLMNOPQRSTUVWXYZ | Alphabet

EKMFLGDQVZNTOWYHXUSPAIBRCJ | Rotor I wiring
AJDKSIRUXBLHWTMCQGZNPYFVOE | Rotor II wiring
BDFHJLCPRTXVZNYEIWGAKMUSQO | Rotor III wiring

YRUHQSLDPXNGOKMIEBFZCWVJAT | Reflector B wiring
ABCDEFGHIJKLMNOPQRSTUVWXYZ | Reflector B wiring

If we now track the first A:

A-E | etw to rotor I
E-A | rotor I to rotor II
A-B | rotor II to rotor III
B-R | Reflector B
R-X | rotor III to rotor II
X-V | rotor II to rotor I
V-I | rotor I to etw

So the output is I instead of B, where is my mistake?

As I noted in this earlier answer to a related question, the rotor permutations in your example are written using a shorthand notation that only shows the output alphabet of the permutation, with the implicit assumption that the input alphabet is always ABCDEFGHIJKLMNOPQRSTUVWXYZ.  That is to say, your rotor descriptions:

EKMFLGDQVZNTOWYHXUSPAIBRCJ | Rotor I wiring
AJDKSIRUXBLHWTMCQGZNPYFVOE | Rotor II wiring
BDFHJLCPRTXVZNYEIWGAKMUSQO | Rotor III wiring

actually describe the following permutations:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ | Rotor I
EKMFLGDQVZNTOWYHXUSPAIBRCJ

ABCDEFGHIJKLMNOPQRSTUVWXYZ
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ | Rotor II
AJDKSIRUXBLHWTMCQGZNPYFVOE

ABCDEFGHIJKLMNOPQRSTUVWXYZ
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ | Rotor III
BDFHJLCPRTXVZNYEIWGAKMUSQO

Also, there are two other issues with your example encryption:

You're applying the rotor permutations in the wrong order; the rotors are conventionally listed from left to right, but the wiring from the input/output to the reflector goes from right to left.  So in your example, rotor III should actually be applied first, then rotor II and finally rotor I (and then the reflector and the inverse rotors in the opposite order).
The rotors are stepped before each letter is encrypted.  So if you start with all rotors in the A position, when the first letter of the message is encrypted the rightmost rotor (i.e. rotor III here) will have already rotated into the B position.  This means you have to shift the letter right by one step in the alphabet before it enters the rotor, and back left by one step after it leaves the rotor.

Put all together, the correct path of the first letter is:

A ⤑ B → D ⤑ C (rotor III in position B)
C ⤑ C → D ⤑ D (rotor II in position A)
D ⤑ D → F ⤑ F (rotor I in position A)
F ↔ S (reflector B)
S ⤑ S → S ⤑ S (rotor I in position A, reverse)
S ⤑ S → E ⤑ E (rotor II in position A, reverse)
E ⤑ F → C ⤑ B (rotor III in position B, reverse)

For each rotor, there are effectively three permutations to apply: an alphabet shift to the rotor's current position (i.e. 0 steps for position A, 1 step for position B, 2 steps for position C, etc.), the fixed rotor wiring permutation and finally the reverse shift back from the rotor's position.

In the list above, I've used a dotted arrow ⤑ for the shifts and a solid arrow → for the rotor wiring permutations (and a two-headed arrow ↔ for the reflector).
 In this example, two of the three rotors are still in position A, so for them, the shifts have no effect, but I've shown them anyway for completeness.  Also, just by chance, the wiring in rotor I happens to map the letter S to itself.


How to compare the time of encryption, cracking and verification elliptic curve problem in the same framework？ everyone! As a beginner, I would like to ask you a question. The best algorithm known for cracking (done by anonymous snooper) this problem （Discrete logarithm problem of elliptic curve or ECDSA）is Pollard’s rho method, and takes about the square root of πp/2, where p is the modulus. My questions are:
(1) Elliptical encryption (done by designer and sender) also takes time. Can this time also be expressed by modulus p?
(2) After the other party receives the information, it needs to be verified. This verification (done by receiver of information) also takes time. Can the time for verification also be expressed by modulus?
That is to say, can the above three kinds of time be put into a frame for comparison, and they are all compared with the parameters of elliptic curve (it is best to use modulus or order of Base point). My intention is to know which of these three times is the slowest and which is the fastest. But there is no doubt that the time to crack is definitely the slowest, and the time for encryption and verification is definitely much shorter. But how to quantify them? Is there any literature recommendation that compares them? It would be best to give a simple example. Thank you very much!

Let $n$ be the number of points in the curve group and $p$ the size of the field. The quoted estimate for Pollard $\rho$ is $\sqrt {\pi n/2}$ which is the number of elliptic curve group operations required. To sign a ECDSA message (assuming that you already have your key pair) is an elliptic curve scalar point multiplication which takes (using windowed double-and-add) $(1+\epsilon)\log n$ elliptic curve group operations. To verify is 2 elliptic curve scalar multiplications which is $(2+\epsilon)\log n$ elliptic curve group operations. If you have to generate a key pair, that adds another elliptic curve scalar multiplication.
The elliptic curve group operation will get harder with $p$ as well and the exact complexity is subject to a range of variant algorithms. An estimate of $O(\log^2p)$ for each elliptic curve group would not be hugely inaccurate though.


Number of generators of an elliptic curve Consider the elliptic curve E:$y^2 = x^3 + 3x + 11\,\, mod\,\, 19$. Two questions:

Let the cardinality of the set of points on the elliptic curve( including
$O$ ) be $|E|  = 25$. How many points are generators and why?
Find an element of this group that has order $5$. The group operation is addition of points.

Answer of (1): First, when the author says points, I assume he is being sloppy and really means group. The number of generators for a cyclic group with $n$ elements in it,
are the number of integers from $[1,n-1]$ that are relatively prime to $n$.
Therefore, in this case, the answer is $19$. Is my answer right?

Regarding question (2): I am thinking about guessing at the answer and doing a brute force approach (maybe doing the brute force approach in software) but it seems to me that there should be a shorter way to do it. Could you comment on my idea?

I think I just found a trick for solving the second question. Let $a$ be a generator of the group. Then I claim that $a^5$ is an element of order $5$. Is my claim correct?

No, he really means the number of points on $E$. So the number of solutions to the given equation plus 1 (for the point at infinity). He also gives the answer as $25.$

You need to apply your idea about number of generators to the correct group size.


How to encrypt data and know it will be secure for at least a few decades? I want to encrypt a small amount (few kilobytes) of data and be fairly confident it will be secure against brute force decryption and advances in cryptanalysis for at least a a few decades (or more). I am flexible on the amount of time it takes (even a minute is reasonable) to encrypt as this will run on the client machine, and not on a server.

My thought was to combine a few encryption algorithms over an iterative process - each iteration with a fresh key. The reasoning being:

Multiple iterations increases the time necessary for each brute force attempt.
Multiple algorithms means a failure in any one algorithm doesn't compromise the whole encryption.
Multiple key effectively increases the key size to astronomical.

So it might look like this:

CipherText = AES(TwoFish(Serpent(PlainText)));

Except with many more layers of nesting (repeating the selected algorithms). Each layer will have a CSRNG generated Key and IV and use CBC.

Is this a good idea?
Does the nesting increase the security, or does it somehow introduce a new vulnerability?
If this is a good idea, which algorithms would be best to use?
Would it be better to use asymmetrical algorithms instead of symmetrical ones?
How many iterations is enough?

I'm fine with it being overkill. Just want to make sure it isn't going to make things worse.

Updated to specify resistance to cryptanalysis, use of CSPRNG for Key and IV and using CBC. Also removed references to outdated algorithms.

Is this a good idea?

Not really.

It is rare to find attacks against vetted designs that allow a complete break with a tiny amount of cipher-text.

Assuming you plan to have a unique key (which isn't used anywhere else) for just this few kilobytes of plaintext, it's very unlikely any cryptographic attack could be mounted against any modern cipher that would recover the plain-text.

Honestly, your message is likely to be absolutely fine encrypted with AES.

It's very unlikely someone's missed a key-recovery attack on AES that can be conducted with a few kilobytes of cipher-text.

  Does the nesting increase the security, or does it somehow introduce a new vulnerability?

It is possible to do this badly and introduce a new vulnerability, yes.

  If this is a good idea, which algorithms would be best to use?

Just use AES in GCM mode.

  Would it be better to use asymmetrical algorithms instead of symmetrical ones?

No.

  How many iterations is enough?

One iteration of AES in GCM mode is enough.


Calculate number of required pairs for differential cryptanalysis I am currently doing some study on differential cryptanalysis.

However, I have two open questions in the field.

The first question is: How can I calculate the number of messages necessary for a successful attack?

I have read that if you have found a concrete characteristic by the cipher with probability $p$ that the number depends directly on $p$, which is understandable. However, I don't know how to calculate the number and more importantly, I can't find any literature (book or paper). If someone has a concrete tip, I would like to read it.

My second question is: Is there a measure for evaluating a probability $p$ of a characteristic? How high (or good) should a probability be for the attack to be successful? Are there any literature recommendations here?

See Heys' Tutorial on Linear and Differential Cryptanalysis (google it) for a gentle introduction.

Ali Aydin Selcuk has carefully analyzed this success probability in a number of papers.

For differential cryptanalysis roughly $c/p$ plaintext ciphertext pairs are needed where $c$ is a small constant dependent on the cipher.

As for your second question, unless $p$ is much larger than about $2^{-80}$ there is no practical attack. After all, you need to encrypt at least as many as $c/p$ plaintext ciphertext pairs to collect data before you can mount the attack and the quantity $c/p$ is a lower bound on at least your time complexity (possibly also your memory complexity depending on your attack).

However a $p$ value that is appreciably larger than $2^{-k}$ where $k$ is the keylength of the block cipher indicates a weakness in that the cipher is weaker than expected, as in Biham and Shamir's attack on DES.


Why is verification using DSA slower than verification with RSA? We read in literature that verification of a digital signature is slower using DSA than if we used RSA. Why is this?

DSA parameter generation:

choose prime number $p$
choose prime number $q$ such that $q \mid (p-1)$
$g = h^{\frac{p-1}{q}}\mod p$ with $1 < h < (p-1)$ (multiplicative order)
private key: choose $x$ such that $0 < x < q$
public key: $y = (g^x\mod p)$

Public key: $(p,q,g,y)$ and private key: $(x)$.

To calculate the signature $(r,s)$:

choose $k$ $(0 < k < q)$
$r = (g^k\mod p)\mod q$
$s = [k^-1 (H(M) + xr)]\mod q$. ($H()$ is our hash function)

To verify our signature we calculate

$w = s^{-1}\mod q$
$u_{1} = [H(M)w]\mod q$
$u_{2} = (rw)\mod q$
$v = [(g^{u_{1}}y^{u_{2}})\mod p]\mod q$

So, I understand how this works. But why is verification slower than RSA verification?

If you compare DSA with SHA-256 and a 2048 bit group modulus $p$, to RSA with SHA-256, a 2048 bit modulus $n$ and public exponent $e = 65537$, on you will at least perform the following operations:

DSA

$g^{u_1}y^{u_2}$ - 2*256 squares $\mod p$, up to on average 2*128 multiplications $\mod p$, depending on implementation optimizations.

RSA

$s^e$ - 16 squares $\mod n$, 1 multiplication $\mod n$.


384-bit ChaCha20 / Salsa20 The standard Salsa20 core is a $\{0,1\}^{384} \to \{0,1\}^{512}$ random function with a 16 byte constant ($\sigma$ for a 32-byte key), an 8 byte nonce, an 8 byte counter, and a 32 byte key. The hash function does not make any distinction between the types of input. This leaves 48 bytes which can be randomly chosen. If they are all chosen randomly and are kept secret, does that increase the keyspace to $2^{384}$, or is there some reason why the internal state of the cipher is limited to 256 bits? I ask this because the Linux kernel random driver (called CRNG) uses ChaCha20 to generate randomness.

The cipher state is initialized in the Linux kernel with the following function:

static void crng_initialize(struct crng_state *crng)
{
    int             i;
    unsigned long   rv;

    memcpy(&crng->state[0], "expand 32-byte k", 16);
    if (crng == &primary_crng)
        _extract_entropy(&input_pool, &crng->state[4],
                         sizeof(__u32) * 12, 0);
    else
        _get_random_bytes(&crng->state[4], sizeof(__u32) * 12);
    for (i = 4; i < 16; i++) {
        if (!arch_get_random_seed_long(&rv) &&
            !arch_get_random_long(&rv))
                rv = random_get_entropy();
        crng->state[i] ^= rv;
    }
    crng->init_time = jiffies - CRNG_RESEED_INTERVAL - 1;
}

The state, kept in (struct crng_state *)crng->state, has the constant $\sigma$ for the first 16 bytes, and the last 48  bytes are generated randomly using _extract_entropy(), a function that returns the amount of entropy requested. Does this mean CRNG output has a $2^{384}$ keyspace?

If there is an attack against ChaCha20 that requires at least $2^{256}$ invocations of the cipher, then increasing the keysize does not increase security (even if 256 is already plenty). In other words, ChaCha20 with a 256-bit key is 256-bit secure, but I do not know if ChaCha20 with a 384-bit key is 384-bit secure. Would there be no attack faster than brute force for a 384-bit key?

I am fully aware that even a good 256-bit cipher is considered impossible to break with modern technology and that there is no practical reason to use a larger key. However sometimes it is useful to know how much entropy is present in a given amount of pseudorandom data.

Yes, you have control over $32$-byte key + $8$-byte nonce + $8$-byte counter totalling to a $384$-bit key and this is perfectly safe.

Your only responsibility for this function is to ensure that the $(\text{Key}, \text{Nonce})$ tuple never repeats. The PRG will increment and wrap the counter so this may start randomized. You can still increment the nonce. You could (but probably shouldn't) increment the key.

Alternatively you can use the much more standard IETF variant of chacha20 with a 96-bit nonce and $32$-bit counter or the Xchacha20 variant with $192$-bit randomized nonces and no exposed counter.

Edit: How are we certain that chacha20 is not capped to 256-bit security?

The constants, key, nonce and counter are all treated equally such that a $1$-$2$ bits changing in the counter is safe. The constants exist to weigh the control of the function away from the adversary. The adversary can control the $8$-byte nonce and $8$-byte counter, not the $32$-byte key nor $16$-byte constant. $16 / 64 = 1 / 4$. If the adversary could control the constants then they have $1 / 2$ of the input. A full $384$-bit key gives the adversary only the public constants worth of knowledge (and they know the counter increments). A $512$-bit key means the adversary knows no inputs.


Is there benefit to signing unencrypted emails? I came to this article from another comment on Crypto StackExchange. After reading it, I am wondering if there is any benefit to using a digital signature on unencrypted S/MIME emails?

Yes, of course there is a benefit to signing unencrypted emails. The article you cite is solely about the combination of signature and encryption; it doesn't directly say anything about signing unencrypted emails.

There is an important concern raised by the article which does apply to unencrypted emails, but that's because that concern applies equally whether the email is encrypted or not. The problem is that only the body of the email is signed. So when you receive a signed email (whether it's encrypted or not), you need to be careful not to implicitly assume anything about the context of the email. For example, when Alice signs “I love you” and sends it to Bob, Eve can forward the message to Charlie; Charlie will then see a signed message, guaranteed to have been written by Alice, and saying “I love you”. Charlie might assume that because he received the email, the “you” in the email is him; but this association is not warranted. All that Charlie can know is that Alice declared her love to someone, but not who that someone is. If Alice had wanted to send an unambiguous message, she should have signed “Dear Bob, I love you”.


Would RSA make sense if we used no computers? I was recently wondering - would RSA be useful if we brought it to, say, medieval times? Could you choose the keys so that you could encrypt/decrypt messages quite easily, but factoring the private key would, say, take over 1000 days for 1000 people, provided that they used paper and pencil only and wouldn't make any mistakes?

I thought about this and have done a bit of research, and the answer is no.
The problem is the gap between the difficulty of factorisation versus prime generation isn't really large enough at the scale of primes/moduli we can work with.
By 1588 the largest prime discovered was 524287, thanks to Pietro Cataldi. This was a prime generated by a single person's work. I don't know how much effort this took, but given that it was a world record at the time, I think we can assume it was a fair amount of effort.
In order to have a secure instance of RSA, we'd probably want to generate a modulus using two six-digit primes. That's already quite a bit of work.
However, a nation-state can draw on more resources. They could hire a team of people to try and break the message. One observation is that there aren't actually that many primes below 1,000,000: there are only 78,498! If we consider only the primes between 100,000 and 1,000,000, this number comes down to 68,906.
A nation-state could use the sieve of Eratosthenes to find all the primes below 1,000,000. This would be a one-off effort.  They would then need to attack any modulus which is the product of two six-digit primes.
Finally, to factor a particular spy's modulus they simply could give it to a pool of people who would work down through the list.
Let's say one person can try one division every five minutes. That seems like quite a long time given the size of the numbers. Nonetheless, in one eight-hour working day, they could try 96 divisions per day. Across a pool of 20 people it would take 35 days to run through the entire list.
In practice, most moduli would be solved much sooner than this because both primes will appear somewhere in the list.
This attack is entirely practical and thus makes RSA pretty useless for encryption in that historical period.


is OPE able to produce different cyphertext for same plaintext? Given a plaintext p, is OPE (Boldyreva et al.) able to produce n different cyphertext c1...cn for the n occurrences of p?
If not, there exists an order-preserving encryption scheme able to do that?

Boldyreva et al.'s scheme is not randomized. However, there is a folklore way to "randomize" it by choosing randomly from the range gap in the last recursive step of the algorithm. It's not clear what security improvement this buys you, though, since it only really randomizes the last few bits of the ciphertext.

There are schemes meeting a randomized version of Boldyreva et al.'s IND-OCPA definition (q.v. Kerschbaum, CCS'15) but they require large client storage.


What do $0^n$ and $1^n$ mean in cryptography? Let $f$ = $\{f_k\}$ be a pseudorandom function family.
Let $G(x)$ be a pseudo-random generator such that:
$G(x) = f_x(0^k)f_x(1^k)$ where $k=|x|$.

I don't understand the meaning of $1^n$  and $0^n$, and the differences between them, in that context.
What do they represent?
What is the special role / effect they have on the above context? And how?
Why $1^n$ and $0^n$, and not other combinations?

Typically that means a string of either $n$ zeros or $n$ ones.


How many bits shift is a TEA encryption? void encrypt (unsigned long* v, unsigned long* k) {

unsigned long v0=v[0], v1=v[1], sum=0, i;           /* set up */
unsigned long delta=0x9e3779b9;                     /* a key schedule constant */
unsigned long k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
for (i=0; i < 32; i++) {                       /* basic cycle start */
    sum += delta;
    v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
    v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
}                                              /* end cycle */
v[0]=v0; v[1]=v1;

}

I saw this code on the wiki of TEA encryption and was wondering is this considered a 4-bit or 5-bit algorithm since there was a shift of 4 bits to the left but a shift of 5 bit to the right.

I am confused on the algorithm of this encryption and would appreciate it if somebody can clarify it for me.

Thank you

TEA is neither considered a 4-bit nor 5-bit algorithm (these are not categorized by their shift count). TEA:

Is a 64-bit block cipher, meaning encrypt modifies 64 bits: the block is v[0] v[1] and the code shown (non-portably) assumes unsigned long is 32-bit.
Has a 128-bit key k[0] k[1] k[2] k[3] ; notice that each key has 3 other equivalent ones (obtained by complementing the high-order bits of even or/and odd numbered words), thus key is effectively 126-bit.
Performs 32 double rounds, with in each double round (focusing on shifts because that's asked) two left shifts by 4 bits and two right shifts by 5 bits (on a 32-bit quantity). That's 128 shifts on a machine with a 32-bit barrel shifter, and 5760 shifts with a 32-bit ALU without barrel shifter.

Addition: the only two common reasons to count the shifts in an algorithm are:

Determine how much computational effort is spent on that, to predict how the CPU influences the performance. Continuing on that track: on 8-bit CPU, 32-bit shifts are quite expensive, and naive code with likely have 23040 shift instructions executed per bloc encrypted, with shifting representing I guess like 3/4 of the effort. In assembly language at least, it is possible to do significantly better by realizing that most bits of v1>>5 can be obtained as ((v1<<4)>>8)>>1, with the shift by 8 efficient on an 8-bit CPU. Also, many 8-bit CPUs have an instruction that swaps the halves of an octet, and might be put to use for the shift by 4.
Determining is there's enough diffusion. In TEA, it is used shift rather than rotations (largely because there is no built-in rotation in the C language, and building one would have made at least the source code more complex), and therefore diffusion across bits of the 32 ranks in 32-bit words is mostly by shifting (exclusively so for right diffusion, and with carry propagation contributing slightly to left diffusion). Full diffusion requires about 8 rounds, and that is significantly slower than say in DES, which diffuses I'd say more than twice faster. That's one of several reasons TEA must have a lot of rounds (64 rounds versus 16 in DES).


Use ElGamal to solve Diffie-Hellman problem Say we are able to decrypt a Elgamal ciphertext $c$ using only the public key. Apparantly it is now possible to solve the Diffie-Hellman problem (given $g^a, g^b$ calculate $g^{ab}$). How?

I know how it works the otherway. When I'm able to solve DH, I found a way to decrypt Elgamal ciphertext. But I can't come up with a good idea for this problem.

I figured since $c=(c_1,c_2)=(v,w)$ maybe $c_1=g^a, c_2=g^b$ such that the plaintext $p=g^{ab}$, but that doesn't work out.

I'm thankful for any tips.

Since you're learning, I won't go ahead and give you the answer; I will try to point you in the right direction.

Consider what Elgamal decryption is: if the private key is $a$ (and hence the public key is $g^a$), and you're given a ciphertext $(b, c)$, the ElGamal decryption is $b^{-a} \cdot c$

Now, assume that we have an Oracle that, given an arbitrary public key $g^x$, and a ciphertext $(g^y, z)$, would return the ElGamal decryption.  Can you see how you could use that by passing it a public key and ciphertext of your choosing (hint: write out what the decryption would look like in that case)?

(Further hint: given $g^x$, it is easy to compute $g^{-x}$, as that's just the multiplicative inverse)


Witness-Extended Emulation I am reading up on Sonic: Zero Knowledge SNARKS from Linear - Sized Universal And Updateable Structured Reference Strings.

An excerpt:

  For soundness, we do not use the standard definition of special soundness because our verifier provides two challenges, but rather the generalized not of witness-extended emulation.

Can anyone provide both a simple and terse explanation of the term
 "witness-extended emulation"

Witness-extended emulation is a more robust notion of knowledge soundness that avoids subtle problems when the proof of knowledge system is used inside of bigger protocols.

For example, suppose you have a two-party protocol between A and B where at some point A provides a PoK for some statement x. (So the PoK is used as a sub protocol inside this bigger protocol.)

Now, to prove that the protocol is secure you want to build a simulator S that simulates a corrupted A. To do so, it produces a view that is the view of A in the protocol, which includes the transcript of the PoK.
Also we can assume that this simulator needs to extract the witness from the PoK (in almost all cases the simulator needs to do so: intuitively, it seems that otherwise this PoK would be kind of useless).

Thus a naive simulator could:
1) Run with A and act as a verifier so to get a transcript of the PoK
2) If the transcript is valid, run the extractor E.

Now, the problem is that for (standard) knowledge soundness we have that the extractor is an expected polynomial time machine that outputs a valid witness and runs in $poly/(p-k)$ where $p$ is the probability that A outputs a valid proof and $k$ is the knowledge error (very roughly speaking, the probability of convincing the verifier by sending random messages).

The problem is that if we compute the expected running time of the simulator S we have that it is at least $p \cdot poly/(p-k)$, which might not be expected polynomial time!

Luckily, Lindell (https://eprint.iacr.org/2001/107.pdf) showed that if you have knowledge sound then you can get witness-extended emulation. So we don't have to worry about.

To summarize, whenever you want to use your PoK inside a bigger protocol it is more convenient to rely on witness extended-emulation (less troubles with the proof of security). While, if the PoK is used stand-alone then both the notion of security are fine.


How to hash a list of multiple items? In some protocols, a key is derived from a hash of many parameters (K=H(param1,param2,param3))

Is there a hash function that takes many parameters as input ?

Or we can simply use a function like SHA-1 by concatenating these parameters as input ?

As tylo correctly notes, when we hash multiple values, the important feature that any method we choose should have is that it should be unambiguous: there should not be any way to construct two valid sets of values that produce the same hash value — or at least it should not be any easier than breaking the collision resistance of the underlying hash function by constructing two strings with the same hash value.

In practice, there are many ways to do this.  Some are only valid for ceratin kinds of inputs:

Plain concatenation of the input values before hashing them can be problematic, since, as tylo notes, e.g. "12" || "3" = "1" || "23".  However, in some special cases it can be safe, e.g. when all the inputs (or all but one of them) are known to have a fixed length, or when there some other way to always tell where one input value ends and the next begins.
Using a separator string works well, if we can guarantee that the separator will never occur in any of the input strings (or at most, that it can only occur in one of them and that the number and order of the inputs is fixed).  When hashing ASCII or UTF-8 text, null bytes are popular separators.

Other methods are more general, and can be used for (almost) any input tuples:

Prepending the length of each input string to it before concatenating them, as suggested by fgrieu in the comments, makes the encoding unambiguous.  One potential issue is that, if a fixed-size length field is used, this limits the length of the allowed input strings.  This can be avoided if a variable-size encoding is used for the length; perhaps the simplest way to do that is to just write the length out as sequence of decimal (or hexadecimal) digits, followed by some non-digit separator.
There are also several existing data serialization formats that have already solved the problem of uniquely encoding arbitrary data structures into strings.  Perhaps the best known example in cryptography is ASN.1 DER, but there are several other alternatives such as csexps.  One advantage of using such a format is that they typically support more complex data structures than just tuples of strings; another is that you can find pre-made encoders instead of having to code your own.
Finally, instead of just encoding the inputs into a single string and hashing it, it's also possible to modify the hashing method to directly support multiple inputs.  One general way to do that is to use a hash list, in which every input value is first hashed separately, and the resulting hashes (which have a fixed length, and can thus be safely concatenated) are then concatenated and hashed together.


Different patterns of different paterns, wildcard I'm not realy experienced with programming and such but I am wondering if the following could be implemented in, lets say, python

we have the following ciphertext sequence

AO AP AL EE IL OP QR IV OD DD GH DK OL FK PO AD GG PO FK OL DK GH OL OT RI DH SK

and I know part of the plaintext says:

risetovotesir

Than for sure, I know that of the chipher text the following part:

[GH DK OL FK PO AD GG PO FK OL DK GH] = risetovotesir

which means GH = 'r' , DK = i

Now, lets say the ciphertext would be 400 times longer but does not have such pattern in it again, is there a way to "search" for such thing ?

I'm sorry if I explained this too vaguely, but I'd be happy if anyone could tell me how this would be possible.

Generally, that is possible.

crypto-analytics

Including solutions that collect statistical information, there are several solutions which are used during cryptographic analytics that can cope with shifting (read: changing) values, frequencies, and pattern detections.

Yet, merely having knowledge of the cyphertext will not be enough most of the time. For example, it's not really helpful when a modern encryption algorithm has been used since such algorithms twist and mix the bits so that it is "near to impossible" to trace or guess how a single bit (or byte) of the message was encrypted.

exploiting partial break

Additionally, you have to count in that - due to the fact your example shows you have part of the plain-text which was used to generate the encrypted message - there are additional hints for analysts that could show how the encrypted message may have been encrypted. This in itself weakens the encrypted text in this specific situation, as it represents a "partial break" which can be build upon.

practical approach

I could go on and practically approach your example to show you step-by-step how I would be able to decode your encrypted message, but while writing this answer I have decided to not do that to prevent going off-topic, because:

  analyzing or decyphering a block of data are off-topic here, as the results are rarely useful to anyone else.

I'm sure you understand.


VeraCrypt a weak point Biggest flaw in VeraCrypt(or other Encryption programs)  is Hash Algorithm.
VeraCrypt hashes (SHA,Whirlpool,Streebog) it is the only point where can break an encrypted disk. Because break algorithm (AES,Towish,Camellia,Serpent,Kuznyechik) it is practically impossible.
VeraCrypt hashes can be broken by Police with the appropriate cash input. Hashcat can break VeraCrypt hashes.

How to protect against it?
Will longer mouse movements help?
And hashes are really so dangerous?

I invite to the discussion.

VeraCrypt hashes can be broken by Police with the appropriate cash input. Hashcat can break VeraCrypt hashes.

Breaking a hash algorithm and brute-forcing a hash input are 2 completely different attacks. Veracrypt uses PBKDF2 with half a million iterations for volume containers, which is an appropriate amount. The weak point which allows recovery of a Veracrypt volume is the strength of the password

  How to protect against it?

Use better passwords and keyfiles, and use a bigger iteration count (PIM)

  Will longer mouse movements help?

No, that has little to do with the password hash strength

  And hashes are really so dangerous?

No, poor choices of passwords and bad opsec are dangerous, it is easier to install hidden cameras and observe keyboard input, or to use torture


ECRYPT Salsa20 Test Vectors Interpretation I am currently implementing Salsa20 for my bachelor thesis. After having verified all the functions needed for the final encryption function with the given test data in the specification from DJB, I wanted to test my encryption function. Unfortunately, there are no test vectors for the full encryption in the specification paper:

I have found test vectors for Salsa20/20 from the ECRYPT Stream cipher project here.

But for some reason, the first 64-byte sequence matches with the output of my expansion function with the given key and IV and counter set to 0 but the second 64-byte sequence differs.

Actual:

0xa360370ff47dd714684fd47584e46fe89e031b59072be978f7c0a56936151a3e9c52f7be26c687a5bc234640efed47b79b02d70dd666dc39cea9288e69427318

Expected:

0x57be81f47b17d9ae7c4ff15429a73e10acf250ed3a90a93c711308a74c6216a9ed84cd126da7f28e8abf8bb63517e1ca98e712f4fb2e1a6aed9fdc73291faa17

I have used the IV 0x0 (64-bit) and counter 0x1 (64-bit) concatenated such that the nonce given to the expansion function is

0x00 00 00 00 00 00 00 00   00 00 00 00 00 00 00 01

(big endian). But this leads to an incorrect result as shown above.

I have tried to write the bytes of the counter in littleendian since the specification paper mentions this in the last section about encryption:

0x00 00 00 00 00 00 00 00    01 00 00 00 00 00 00 00

but that only lead to a different wrong result:

0x8da2b74eef1b6283e7e20166abcae538e9716e4669e2816b6b20c5c356802001cc1403a9a117d12a2669f456366d6ebb0f1246f1265150f793cdb4b253e348ae

I am assuming I am interpreting the test data incorrectly since my expansion function passes all the tests with the test data given in the specs.

I have found out here that the test vectors are using the NESSIE format but couldn't find a explanation about the data which solves my problem (probably there is no explanation because I am doing something quite obvious wrong?)

I am also confused what "(stream is generated by encrypting 512 zero bytes)" should mean. The stream is independent from the plaintext thus I am wondering what they mean by that it "is generated by encrypting 512 zero bytes"?

I would be very glad if anyone could help or lead me into the right direction since I am stuck with this for quite some days already. :)

Your "different wrong result" (based on a littleendian counter) appears to be the correct second 64-byte sequence.  The test vector shows "stream[192..255] = ", which is the fourth 64-byte sequence.  The test vector is generated by calling "the Salsa20 encryption function" (Section 10 of the spec) on 512 zero bytes using the indicated key and IV.


Comparing Shanks' Algorithm to Brute Force I'm trying to understand how/why Shanks' algorithm solves the discrete log problem $y=g^x \bmod p$ faster than a brute force search does. Any explanation would be great.

Shanks' algorithm—also known as baby-step, giant-step, or BSGS, and known well before Shanks (English translation)—does not solve the discrete log problem faster than a brute force search, because it is an example of a generic or brute force search algorithm.  Actually it's costlier than other generic algorithms like Pollard's $\rho$, in the standard area*time cost metric that serves as a good proxy for number of joules or number of rubles you would have to spend on the computation.

Fix a group $G$ and an element $g \in G$ of prime order $\ell$.  Suppose you can compute the functions $(a, b) \mapsto a \cdot b$, $a \mapsto a^{-1}$, and $(a, b) \mapsto [a = b]$ on elements of $G$; that is, you can compute the group operation and inverse, and you can test elements for equality.  If $h = g^x$ for a uniform random exponent $x$, how can we find $x$?

This setting—where you can compute products and test equality but you know nothing else about $G$—is the generic setting; attacks in this setting are sometimes called generic attacks or brute force attacks.  If we had specific knowledge about $G$, like we do when $G = (\mathbb Z/p\mathbb Z)^\times$ for prime $p$, we might have better attacks, like index calculus with the NFS.  But we are in the generic setting.

Naive approach.
One option is to try $x = 0$ and check whether $h$ is $1$, then try $x = 1$ and check whether $g$ is $h$, then try $x = 2$ and check whether $g^2$ gives $h$, then try $x = 3$ and check whether $g^3$ gives $h$, etc.  If $x$ is uniformly distributed, the expected number of trials is $\ell/2 = O(\ell)$.  To save effort in each trial, rather than computing $g^k$ afresh each time, we can store state $s_k = g^k$ and update it by $s_{k + 1} = s_k \cdot g$ with a single multiplication.  This is the naivest approach.  Can we do a better brute force attack?

Pairwise grouping.
Consider grouping the trials into pairs:

Is $h$ either $1$ or $g$?
Is $h$ either $g^2$ or $g^3$?
Is $h$ either $g^4$ or $g^5$?
Is $h$ either $g^6$ or $g^7$?

⋮

If we succeed on the $k^{\mathit{th}}$ trial, we need only determine whether $x = 2k$ or $x = 2k + 1$.  The expected number of trials is $\ell/4$, plus a little extra work at the end.  Of course, each trial costs twice as much as before, so this doesn't win anything yet.

Common criterion.
Rather than compare $h$ to $g^{2k}$ and $g^{2k + 1}$, we can compare $h g^{-2k}$ to $g^0 = 1$ and $g^1 = g$, so that each trial performs the same test.

Is $h$ either $1$ or $g$?
Is $h g^{-2}$ either $1$ or $g$?
Is $h g^{-4}$ either $1$ or $g$?
Is $h g^{-6}$ either $1$ or $g$?

⋮

Once we have found $k$ and $\alpha$ so that $h g^{-2k} = g^{x - 2k} = g^\alpha$ and thus $x - 2 k \equiv \alpha \pmod \ell$, we can solve for $x$ as before.  The expected number of trials is still $\ell/4$, but we can precompute $g^{-2}$, and then keep a running state $s_k = h g^{-2k}$ which we can update to $s_{k + 1} = s_k \cdot g^{-2}$ by a single multiplication.  The expected number of trials is about half the naive algorithm, and the number of multiplications per trial is the same, so the expected number of multiplications is $\ell/4$, half that for the naive algorithm.  Of course, we have to do two equality comparisons for each trial, but an equality comparison is probably cheaper than a multiplication.

Wider grouping.
If a table lookup had the same cost as an equality comparison, we could make a table of $m$ different entries by precomputing $1, g, g^2, g^3, \dots, g^{m - 1}$, precomputing $g^{-m}$, and then searching as before:

Is $h$ in the table $\{1, g, g^2, \dots, g^{m - 1}\}$?
Is $h g^{-m}$ in the table $\{1, g, g^2, \dots, g^{m - 1}\}$?
Is $h g^{-2m}$ in the table $\{1, g, g^2, \dots, g^{m - 1}\}$?
Is $h g^{-3m}$ in the table $\{1, g, g^2, \dots, g^{m - 1}\}$?

⋮

Once we have found $k$ and $\alpha$ so that $h g^{-k m} = g^{x - k m} = g^\alpha$ and thus $x - k m \equiv \alpha \pmod \ell$, then we can solve for $x$ as before.  Also as before, we can update the state $s_k = h g^{-km}$ with one multiplication $s_{k + 1} = s_k \cdot g^{-m}$.  The expected number of trials is $\ell/(2m)$ and the cost of each trial is (a) one multiplication and (b) one table lookup.  Thus the expected number of multiplications and table operations is $O(m + \ell/m)$, which is optimized by $m = \sqrt\ell$.

Caveat.
In real computers, storing tables costs energy and table lookups cost more time and energy than equality comparisons.  So BSGS's apparent ‘cost’ of $O(\sqrt\ell)$ multiplications, which seems to be an improvement on the naive algorithm's $O(\ell)$, is misleading in practical terms because it uses an unrealistic cost model where storage is free and an equality test costs the same as a table lookup.  Pollard's $\rho$ is a generic brute force algorithm that actually improves the cost in realistic cost models to $O(\sqrt\ell)$: it too runs in $O(\sqrt\ell)$ computation time, but it has constant space requirements and no table lookups, and as a bonus it can be parallelized to take advantage of extra die area to speed it up without changing the net cost.