Finding non-zero coefficients in 8 bit polynomial LFSR I have a following crypto problem and I have been struggling with for some time

An 8-bit linear feedback shift register with connection polynomial
C(X) = 1+aX +bX^2 +cX^3 +dX^4 +eX^5 + fX^6 +gX^7 +hX^8
is used to generate a pseudo-random binary sequence. This pseudo-random
sequence is used as the enciphering key of a stream cipher. It is known that
when the cipher is applied to the plaintext string
[0,0,0,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,1,1,0,1,0,1,1,0,1,1,0,1]
the corresponding ciphertext string is
[1,0,1,0,1,1,0,0,1,1,0,1,1,0,1,1,1,1,1,1,0,1,0,1,0,0,0,1,0,0]

What would be the approach to determine all non-zero coefficients in this polynomial? I have no clue how to start...

Thanks in advance

Berlekamp Massey algorithm does this for you.

See Dilip Sarwate's nice answer


Unbalanced numeric Feistel network implementation After reading a comprehensive paper [1] covering various kinds of generalized Feistel networks, I've tried to implement the Unbalanced Numeric Feistel variant, which relies on modular arithmetic for splitting and joining an integer in two smaller parts.
Given the scarcity of example implementations for this kind of cipher, I had to figure out some inexplicit details on my own in order to come up with the algorithm below. Therefore, I would like to pose some questions to clarify my remaining doubts:

Does the implementation below follow accurately the described network generalization? If not, what operations are wrong and what would be the right way of performing them?

Is there any way of reversing the modulus addition ⊞ on the encryption function other than by using modulus subtraction ⊟ on the decryption function? Given two integers $a$ and $b$ from a finite field of length $x$, the operation $(-a-b) \bmod x$ would be reversible in a similar way to the bitwise exclusive-or, but (obviously) the ciphertext would not be the same as the one obtained with the current operations.

What would be the implications of dynamically computing $first$ and $second$ so the $first \cdot second$ finite field is strictly equal to the input $data$?

Algorithm
Given two finite fields of lengths $first$ and $second$ greater than $2$, a number of $rounds$ greater than $2$, a positive integer $data$ on the finite field of length $first \cdot second$ and a positive integer $key$:

Please note that the LaTeX code above was inserted as an image due to the  technical limitations of the MathJax formatting. The markdown source of this question contains a commented-out block with the code used to render it.
Tests
(Python implementation that can be used to test the described algorithm).
import random

class NumericFeistel:

    def __init__(self, key: int, rounds: int, first: int, second: int):
        assert all(number >= 2 for number in (rounds, first, second))
        self.first, self.second = first, second
        self.key, self.rounds = key, rounds

    def function(self, data: int, round: int) -> int:
        globals().update(self.__dict__)
        random.seed(data + key + round)
        return random.choice(range(first))

    def encrypt(self, data: int) -> int:
        globals().update(self.__dict__)
        assert data < first * second
        for round in range(rounds):
            left, right = data // second, data % second
            left += self.function(right, round)
            data = first * (right % second) + (left % first)
        return data

    def decrypt(self, data: int) -> int:
        globals().update(self.__dict__)
        assert data < first * second
        for round in reversed(range(rounds)):
            left, right = data % first, data // first
            left -= self.function(right, round)
            data = second * (left % first) + (right % second)
        return data

for test in range(1000):
    random.seed()
    feistel = NumericFeistel(
        rounds = 2 + random.choice(range(1000)),
        first = 2 + random.choice(range(1000)),
        second = 2 + random.choice(range(1000)),
        key = 42
        )
    data = random.choice(range(feistel.first * feistel.second))
    assert feistel.decrypt(feistel.encrypt(data)) == data

Weaknesses
Using and abusing the random module for producing pseudorandom numbers and implementing the one-way round function may be a really bad idea, but this code is intended to be as readable as possible, and its hypothetical insecurity is a minor concern.
Please note that this only is a recreational exercise and nobody plans to use it for anything but demonstrative purposes. This is not another rolling out my own crypto question.
Bibliography

Hoang V.T., Rogaway P. (2010) On Generalized Feistel Networks. In: Rabin T. (eds) Advances in Cryptology – CRYPTO 2010. CRYPTO 2010. Lecture Notes in Computer Science, vol 6223. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-14623-7_33

Does the implementation follow accurately the described network generalization?

No. The Feistel network analyzed in the paper assumes independent round functions, but the code does not give that.
The issue is where the code reads random.seed(input + key + round). The corresponding pseudocode either has the same issue, or is at at least ambiguous with
$$\text{return }\mathit{hash}(\mathit{data}+\mathit{key}+\mathit{round})$$
when perhaps it means
$$\text{return }\mathit{hash}(\widehat{\mathit{data}}\mathbin\|\widehat{\mathit{key}}\mathbin\|\widehat{\mathit{round}})$$
where $\widehat x$ is a representation of integer $x$ per (say) big-endian binary, over a fixed-width bitstring chosen large enough for the maximum possible value.
If we use the same hash at each round, it is desirable that the input of $\mathit{hash}$ is unique for any triple $(\mathit{data},\mathit{key},\mathit{round})$. We can do this with just numbers, as
$$\text{return }\mathit{hash}(\mathit{data}+(\mathit{key}\cdot\mathit{nbrounds}+\mathit{round})\cdot\mathit{second})$$
Problem with the current proposition is: there is very little difference in the round functions for the different rounds. For a fixed $\mathit{key}$, if we note $F$ the function $x\mapsto\mathit{hash}(\mathit{key}+x)$, then the Feistel round function $F_i$ at round $i$ is $x\mapsto F_i(x)=F(i+x)$, which is very far from independent functions.
This is a good context for slide attack when $\mathit{first}=\mathit{second}$ and these are small (that is, $2^\mathit{first}$ is enumerable). At least a related-key attack works: no mater how many rounds, we can query two black boxes that implement the cipher and tell if they have their keys offset by one or not. And because the round function's result is added, which is associative with the $i+x$ operation at the input of $F$, I think it extends to a distinguishing attack in the single random key setup; perhaps even a way to tabulate the $F$ function and recover the functional equivalent of the key in sizably less than $4^\mathit{first}$ queries.

Is there any way of reversing the modulus addition ⊞ on the encryption function other than by using modulus subtraction ⊟ on the decryption function?

I see nothing simpler that works.

What would be the security implications of dynamically computing $\mathit{first}$ and $\mathit{second}$ as the $\mathit{first}\cdot\mathit{second}$ finite field is strictly equal to the input $\mathit{data}$?

As is, with $\mathit{data}$ the input block, that's not functional. This would mean the maximum value of the ciphertext is $\mathit{data}$. Thus, by induction, either the cipher is identity (which it won't be in all likelyhood), or it is not injective thus is not decipherable.
Therefore, we can't do without at least another input, which is the $\mathit{top}$ of the range $[0,\mathit{top})$ for $\mathit{data}$. And then we have a serious problem when $\mathit{top}$ is prime.
In Format Preserving Encryption (the academic name of what the question studies), one standard solution to this is cycle walking, which essentially increases $\mathit{top}$ a little until finding $\mathit{top'}=\mathit{first}\cdot\mathit{second}$ with $\min(\mathit{first},\mathit{second})$ above some reasonableness thresold, then fixes encryption by encrypting again when the ciphertext is in range $[\mathit{top},\mathit{top'})$. That's compensated at decryption by decrypting again when the decrypted plaintext is in range $[\mathit{top},\mathit{top'})$.

I have not touched side channel attacks, which are heavily language-dependent anyway.


IND-CCA secure symmetric encryption Although this question maybe looks silly, I have searched similar questions in this forum and googled it but got no desired answers.
IND-CCA security has already been deeply studied in public cryptography. And it is also known that some symmetric constructions (e.g. CBC model) are not IND-CCA secure (for example, see this chapter). However, I didn't find so many results about IND-CCA secure symmetric encryption. The only construction I found is the one provided by Desai in Crypto2000
I was wondering, are there any other well-known constructions of IND-CCA secure symmetric encryption (classical secure)?
Besides, could they still be easily converted to a post-quantum version (for example, by double the length of the secret key)?

In Authenticated Encryption, the authors explained the framework and constructions for Authentication Encryption in detail.
In particular, In Theorem 3.2 they stated that "INT-CTXT" security together with "IND-CPA" security implies "IND-CCA" security.
Then, they introduced a general approach to an "Encrypt-then-MAC" construction that achieves both "INT-CTXT" and "IND-CPA" security, which further implies "IND-CCA" security.
Lastly, thanks for the comment given by @DannyNiu.


What is the shortest ciphertext size output by FHE? Assume we use batching and modulus switching techniques to reduce the size of ciphertext in fully homomorphic encryption (FHE).

Question: What is the shortest ciphertext bit-size output by the most efficient fully homomorphic encryption?

Remark: I'm aware that there're different FHE schemes. I'd like to see what is the shortest ciphertext we can get (even using the above techniques) from an efficient FHE that outputs the shortest ciphertext.

It depends on whether you want to encrypt a single bit, or many bits.

If you want to encrypt a single bit, I think (disclaimer: I might be missing other schemes) that the shortest ciphertexts are achieved by the TLWE-based FHE of this paper (see also this paper on which it is based). According to their claim, the ciphertext expansion is "only" 10000 bits (i.e., encrypting one bit requires 10000 bits). This is because they can simply work with LWE-like ciphertexts, and then transform them when needed into a GSW ciphertext (which supports fully homomorphic operations).

If, however, you want to encrypt multiple bits, then any FHE scheme can achieve optimal rate of $1+o(1)$ using a standard hybrid encryption: an encryption of an $n$ bit plaintext $m_1, \cdots, m_n$ is $(\mathsf{FHE}(K), \mathsf{SymEnc}_K(m_1, \cdots m_n))$, where $\mathsf{SymEnc}_K$ is a secret-key encryption scheme with secret key $K$. To evaluate a function homomorphically on this ciphertext, simply homomorphically apply first the following circuit $C$ to $\mathsf{FHE}(K)$: $C$ has $E = \mathsf{SymEnc}_K(m_1, \cdots m_n)$ hardcoded in its description, and on input $K$, it outputs $\mathsf{SymDec}_K(E)$. Hence, this steps gives you $\mathsf{FHE}(C(K)) = \mathsf{FHE}(\mathsf{SymDec}_K(E)) = \mathsf{FHE}(m_1, \cdots m_n)$, from which you can then evaluate any function of your choice. The ciphertext size is then $n + O(\lambda)$, where $\lambda$ is a security parameter, assuming $\mathsf{SymEnc}_K$ has rate $1+o(1)$ (which is the case with every modern symmetric encryption scheme, e.g. AES).


Is there any way to test how secure is a new cryptosystem? I have investigated Elliptic Curves and after that I have designed a cryptosystem using this technique. How can I test the safety of my scheme compared to another cryptosystems that use factoring such as RSA? There's a way to ensure that my cryptosystem can be used in commercial environment ?

The general answer given to all budding cryptographers is "don't."  Your system is not secure and will be trivially broken if anyone starts using it.

This advice is given out in general because it handles the 99% case.  99% of the time, people who think they have a good algorithm are simply wrong.

Now the cases that remain are the individuals with enough drive to actually learn cryptography.  There's still a very good chance that the first system these people put together has major holes, but there's a big difference between them and the 99%: they're willing to take the time to be objective and learn how to do it properly.

For those, I refer to a famous quote: "Any idiot can design a cryptographic system that they themselves cannot break."  Your system will not be considered secure until others have beaten on it.  Ideally, big names need to beat on it.  However, therein lies a conundrum.  It is far easier to develop a bad cryptographic system than to prove that it's bad.  The big names in the business don't have time to spend on your algorithm until they have a reason to believe it isn't trivially weak.

This is a chicken and the egg problem.  You can't get your algorithm accepted without the big names agreeing it's secure, and the big names wont look at it until your algorithm has seen some acceptance.  What are you to do?

The standard accepted answer in the industry is that, while it means little if someone says "hey, I think I have a good cryptographic algorithm," it means far more if someone with a name for themselves says it.  The community has an accepted way to build a name for yourself: breaking the algorithms of others.  If you want your algorithm to be taken seriously, you first prove that you're the kind of person who knows how to brutally attack their algorithm by showing how well you can break others.

Bruce Schneier, one of those "big names," put together an online self-paced course on this topic.  It's titled A Self-Study Course in Block-Cypher Cryptanalysis.  It consists of several dozen broken algorithms which he has carefully arranged in what he perceives to be an order of difficulty.  In the case of most of them, the task is simple:

Become familiar with a particular (broken) algorithm.
Read a paper about how that algorithm was broken.
Break the algorithm yourself, following the general path laid out by the paper

It's a sort of "following in the footsteps of giants" approach.  It introduces you to a wide array of attacks and encourages you to not only know they exist, but have experience working them.  This way, you are in a good position to try to apply those attacks to your own algorithms.

Once you go through the course, try to find publications of algorithms which have not been broken yet, but do not have the notoriety needed for the big names to go after them.  Break those, publish your results.  This will begin building up your name, and eventually you will be taken seriously when you put forth your own algorithms.

The path to a secure algorithm is long an arduous.  Consider the path undertaken by SHA-3:

Submissions for the NIST hash competition were accepted in 2008.  The total number of submissions is not known because some were rejected before they were even let into the first round.  There were 57 publicly known submissions, 6 of which were rejected outright with no further explanation.
The first round, with 51 submissions were officially announced on December 9, 2008.  There was a conference in February where the algorithms were presented and NIST's criteria for acceptance to round 2 was publicized.  The round ended on July 24, 2009 when NIST published the list of algorithms which made the cut:

10 algorithms were officially withdrawn from the competition after their authors conceded substantial weaknesses.  NIST considers all of these algorithms "broken in round 1"
16 algorithms were not officially conceded, but significant cryptographic weaknesses were found.  NIST considers all of these algorithms "broken in round 1"
11 algorithms were not accepted into round 2.  These were not conceded, and there were no glaring weaknesses.  However, in the name of efficiency of the competition, they were rejected.  Some were rejected because they appeared to be weaker than the others (yet not broken). Some were rejected due to performance issues.  NIST does not consider these algorithms "broken."

14 algorithms were accepted into round 2, down from 53.

Round 2 was a lot more demanding.  Now these algorithms had substantially more attention put on them.  The community was given a year and a half to attack these algorithms, publicizing the final round of advancements on December 10, 2010

9 algorithms were rejected, though NIST points out that none of them were considered "broken" during that period.  They just didn't make the cut.
5 algorithms were accepted into the final around.

The final round lasted almost 2 years, with the winner announced on October 2, 2012.  The entire cryptographic community was paying attention to this, with big names trying to break every one of these 5 algorithms.  In the end, Keccak was chosen as the victor, and is now known as SHA-3

So when you compare the security of your system to a "big name" cryptographic algorithm like RSA, be aware.  This is the kind of scrutiny that the algorithms go under.  If you enjoy that kind of thrill, I highly recommend going through Schneier's self-taught course.  And who knows.  Maybe your algorithm will be the one in a million that is truly secure!  You never know unless you try.

As an aside, you mentioned that you are using Elliptic Curves.  In that particular field, make sure you pay attention to the backdoor issues brought up by Dual EC DRBG.  Those algorithms in particular will be given extra scrutiny for backdoors because of how public the issues of Dual EC were.  You will want to take extra care to make sure the public is aware that your numbers were chosen in an acceptable quasi-random manner (taking digits of pi or e are popular)


Why is RSA encryption performed in mod n, but computation of inverse in $\bmod \varphi(n)$ I am studying the principles of RSA and have come across some unintuitive statements. Lets revisit the RSA algorithm:

RSA Key Generation

Output: public key: $k_{pub} = (n,e)$ and private key: $k_{pr} = (d)$

Choose two large primes $p$ and $q$.
Compute $n$ = $pq$.
Compute $\varphi(n) = (p−1)(q−1)$.
Select the public exponent $e \in \{1,2,\ldots,\varphi(n)−1\}$ such that
$\gcd(e,\varphi(n)) = 1.$
Compute the private key $d$ such that
$d\cdot e \equiv 1 \bmod \varphi(n)$

Decryption:
$x=d_{kpr}(y)\equiv y^{d} \bmod n$

Encryption:
$y=e_{kpub}(x)\equiv x^{e} \bmod n$

I don't find intuitive on why we perform encryption and decryption in modulus $n$, but compute the inverse of $e$ in modulus $\varphi(n)$. Any help is appreciated.

What's relevant here is that the Carmichael totient $\lambda(n) = \operatorname{lcm}(p-1, q-1)$ is the exponent of the multiplicative group of integers modulo $n$, i.e. the smallest positive integer such that $x^{\lambda(n)} \equiv 1 \pmod n$ for all $x$.*

This means that if $ed$ is one more than an integer multiple of $\lambda(n)$, i.e. if $ed \equiv 1 \pmod{\lambda(n)}$ or, equivalently, if $ed = k\lambda(n)+1$ for some integer $k$, then $$x^{ed} = x^{k\lambda(n)+1} = (x^{\lambda(n)})^k x \equiv 1^kx = x \pmod n.$$

(Of course, the Euler totient $\varphi(n) = (p-1)(q-1)$ is itself an integer multiple of $\lambda(n)$, so $ed \equiv 1 \pmod{\varphi(n)}$ implies $ed \equiv 1 \pmod{\lambda(n)}$.)

*) To be precise, $x^{\lambda(n)} \equiv 1 \pmod n$ only holds for $x$ coprime with $n$, since if $x$ shares a prime factor with $n$, it won't be invertible modulo $n$ and no power of it can be congruent to $1$ modulo $n$.  That's why the definition of the modular multiplicative group requires the elements to be coprime to the modulus.  However, the slightly weaker congruence $x^{\lambda(n)+1} \equiv x \pmod n$ does hold for all $x$ as long as $n$ is squarefree, and that's all we really need for RSA.  Not to mention that finding a positive $x < n$ that's not coprime to the modulus $n$ is literally equivalent to factoring $n$.


How can two (or more) parties share and agree upon a common random seed? I really don't know how to call this simple problem: Two (or more) parties need to establish a common (non-secret) value to be used as a seed for a deterministic RNG. The only requirement is that each party can be sure that the seed is really random.

My idea is as follows:

Each party generates a random value $x_i$,
sends its hash $h(x_i)$ to everyone else,
and waits for hashes from all other parties.
Then each party sends its original value $x_i$ to everyone else,
waits for all the values,
and verifies them.
Finally, each party computes the seed as $\mathop\oplus\limits_i x_i$

I know that inventing protocols should be left to experts, however, I'm curious if this could work and what's needed for the this. I see that the generated values must be long enough to avoid brute-forcing and that $h$ must be collision-resistant.

This is pretty much the schoolbook implementation of a shared random number generation (generate, commit, publish). So yeah, it's secure. But this only works for large random numbers, here's a small adaption that allows for arbitrary size integers:

If you need an $n$-bit random number everyone should generate $n$-bit random numbers - this is independent of the security level of the exchange itself. Then everyone also generates a second random number $m$, which is large (say, 256-bit)  to prevent bruteforcing, and publish $H(n || m)$. Then after everyone has commited everyone publishes their $m$ and $n$, but only use $n$ for the XOR-sum.

I'd suggest you to use a 256-bit hash for the commitments.

Beware of all kinds of nastyness with MITM and replay attacks, make sure you do all of this over authenticated channels.


Is it possible to alter the plaintext message without altering the ciphertext? Is it possible to alter the contents of a plaintext message without altering the ciphertext? Altering the private key is allowed to accomplish this. If the answer is yes, how would I go about in doing this? Encryption strength is not particularly important.

Yes, but typically not in any controlled way.
Essentially you're asking whether two different encryption parameterisations map to the same ciphertext space and that is precisely what most cryptosystems do.
Let's take AES-ECB as an example. Suppose that I have a key $k_0$ and a plaintext $P_0$ and a ciphertext $C=\mathrm{AES}_{\mathrm Enc}(k_0,P_0)$. Now I can pick any other key $k_1$ and compute $P_1\mathrm{AES}_{\mathrm Dec}(k_1,C)$ and lo and behold $C=\mathrm{AES}_{\mathrm Enc}(k_1,P_1)$. However $P_1$ is almost certainly gibberish. To try and control $P_1$ is to say I have a matched plain and cipher and want to find the corresponding key. This is intended to be hard.
To take a public key example, let's consider El Gamal on an arbitrary additive group $\langle G\rangle$. Pick a private key $a$ and public key $A=aG$ and off we go. For a plaintext message $M_0$ some one chooses a random $r$ and sends $(R,C)=(rG,rA+M_0)$. Now choose any other private key $b$ which would have corresponding public key $B=bG$ and we decrypt $(R,C)$ using this key to get $C-rB$ which we call $M_1$. Note that $M_1=M_0+r(B-A)$ so to select $M_1$ I need to know $r$ which would involve solving a discrete logarithm.
There is one cryptosystem where the alternative plaintext can be pretty much completely specified and that is the one-time pad. It's a straightforward exercise to show that any OTP cryptogram can be written as any plaintext message of the same length enciphered with a different OTP which differs from the original OTP by the difference of the messages.


Why isn't data encrypted with mutiple ciphers? Why isn't data encrypted with multiple uncompromised (so far) ciphers? Feel free to answer for a single private key for both and separate private keys.

For example, encrypting data with TwoFish and then AES?

Is it a matter of doubling resource consumption vs a small security improvement? Can two ciphers together be weaker than either cipher separately (in practice or theory)?

If the latter, why not apply one cipher to the data and one to a one time pad and transmit both? ( Can a message and one time pad each encrypted with separate ciphers be weaker than the stronger of either cipher? )

If I understand 2DES doesn't give you nearly the bump in security you'd think it would vs 3DES. But IIRC 2DES is still stronger than DES.

Why isn't data encrypted with multiple uncompromised (so far) ciphers?

Since about 1980, when modern widely deployed symmetric encryption actually fails on the field, that's not due to a theoretical break of the cipher, because the art/science of making ciphers has matured¹,². Successful attacks are on compromised or leaking implementations, key management/generation, short keys (perhaps deliberately³), operating mode, and human factors, which are issues that multiple ciphers do not solve. Hence multiple ciphers would only guard against a risk that now fails to materialize.
Before about 1990-2000, strong crypto was illegal for civilians or discouraged, including in many western countries. Thus multiple cascaded ciphers could not be widely⁴ used in commercial products when they where most useful: before the knowledge to make good crypto became commonplace.
Multiple ciphers add complication, and complex systems fail more.
Multiple ciphers increase the computational cost of encryption, and the cost of hardware when hardware is used (as is increasingly the case for AES, the de-facto standard for built-in-CPU cipher nowadays).
If multiple cascaded ciphers use the same key, the security can become that of the weakest cipher, especially against side-channel attacks, which are among the ones that do happen. Therefore we need multiple keys for multiple ciphers, which goes against usability, or/and introduces more complexity.

¹ The closest thing to an exception is RC4, but most actual attacks against systems using RC4 are due to poor key management/operating mode. Also, RC4 was initially used for applications with 40-bit security.

² Asymmetric encryption, signature, and hashes matured later, say 2000.

³ That's why DES has a 56-bit keys, see this. Another example is GSM's A5/1, which is breakable mostly because it uses a small state, presumably because authorities wanted to be able to break it (though I lack a clear reference proving that assertion).

⁴ There are a few examples of cascaded encryption used in disk encryption products where it is an option to damp paranoia / an accessory for security theater. It's an option in  TrueCrypt/VeraCrypt, and the successful attacks against this product work irrespective of use of this option.


Given a private RSA key, how do we get the public key? Is it possible to pre-choose a private RSA key, then obtain a public key from it?

Yes, in general the private key is generated at the same time as the public key in RSA, first the $p$, $q$ primes, then $n = pq$, then the public exponent $e$ and finally the private exponent $d$.

If the private key is given as $(p, q, d$) then you can recover the public key easily. As long as you know the public exponent and $n$, you have the public key (and this means that if you cannot guess $e$, you need $d$ and the factorization of $n$, this is an instance of the RSA problem).

However, as @fgrieu points out, if the private key is stored as $(n, d)$ and $e$ is not conventionally chosen and unknown, then the public key is lost and cannot be obtained from the private key.

The opposite (private key from public key) is meant to be infeasible though.


Does the Balloon hashing paper deprecate Argon2? Does the recent Balloon hashing paper and the included attack on Argon2 effectively negate the result of the Password Hashing Competition? On one hand it seems that only a constant-factor improvement has been achieved, which is rarely critical in cryptography. On the other hand, the entire point of password hashing is to increase the constant factors of brute-force search.

I'm building a new authentication service at the time of this writing; should one use Argon2 or Balloon hashing in new development given this result? (I love the simplicity of Balloon hashing and it comes with a proof, but it hasn't been "selected as a standard").

Does the recent Balloon hashing paper and the included attack on
  Argon2 effectively negate the result of the Password Hashing
  Competition?

No.
The main result of the PHC was not a single new fancy password hashing function (i.e. Argon2), but a massive advancement in the research of password hashing. We understand password hashing and how to do it much better after the competition than we did before it. That's the most important and main result.
Examples of this include new security reductions for time-memory trade-offs (Catena) and completely new ideas like workload delegation (Makwa).

Now for the actual attack. It appears that the attack reduces the time-memory product of one- and two-pass Argon2i (as of v1.2.1) by a factor of 5 (or less). While this is certainly not good, it doesn't completely destroy Argon2i either. So you can still use it, but have to keep in mind that there may be trade-offs against it.

Now for the mitigations:

After this very paper was released, there was an update to the Argon2 specification, adding the paragraph 5.2 to the security analysis, they documented the TL;DR of the attack and how they mitigated it in version 1.3. With Argon2 v1.3 you only need to avoid single-pass Argon2i, with two-passes and more the attack shouldn't apply anymore.
The idea of Argon2i originally was to allow for data-independent memory-hard password hashing, especially to avoid side-channel attacks like cache-timing attacks. However, if your threat model doesn't include attackers sitting on your machine while you're doing the password hashing, you should use Argon2d anyways, which uses data-dependent operations (similar to scrypt) and is not affected by these recent attacks.
The last mitigation of course is to use other password hashing functions. Either the special recognitions from PHC (i.e. Lyra2, Catena, yescrypt and Makwa) or the good old ones like scrypt and bcrypt. Of course you should note that while the old ones have probably seen more scrutiny, they have their own respective weaknesses (e.g. bcrypt doesn't help much against FPGAs and scrypt also has some weaknesses and doesn't protect against side-channel attacks too well either).

In the comments to the question were also two other papers mentioned. "Efficiently Computing Data-Independent Memory-Hard Functions" by Alwen and Blocki which provides asymptotic bounds on the time-memory-product for a variety of password hashing constructs (including Argon2i, Catena and Balloon Hashing).
The other paper mentioned, "Towards Practical Attacks on Argon2i and Balloon Hashing" by Alwen and Blocki improves on the result of the previous paper, focusing on the old and the new Argon2i version and on Balloon Hashing, again reporting successful (conretely instantiated) attacks on both schemes and noting that 10 passes would be required to regain (full) security for Argon2i.

TL;DR: Use Argon2d if you don't mind with side-channel attacks and use high-pass-counted (e.g. 10 passes) Argon2i if you do mind.


Sponge with PRF instead of PRP In most uses of Sponge mode of operations such as SHA3 and many of the round-2 candidates in the NIST lightweight cryptography project, the underlaying primitive is a cryptographic permutation - that is, it's bijective.

For reasons of curiosity, I noticed that a proposed Sponge-based PRNG implement forward secrecy (back-tracing resistance) by truncating part of the permutation state to all-bits-zero (Section 4.3 of the linked paper).

This got me wonder, what if the permutation is one-way (e.g. $p(x) \oplus x$):

Q1: What are the security implications if SHA3 hash and XOF functions were built on top of Sponge-PRF?

Q2: If the proposed PRNG used PRF, how would the security proof break apart?

Q3: If sponge-based duplex AEADs used PRF, how would their security proof break apart?

I sent a mail to the Keccak team asking about this, and I got a response from one of the authors (Joan Daemen to be specific).

According to him, we actually can instantiate Sponge functions and Duplex objects with a "transformation" in addition to a permutation, the latter of which is what we commonly do. As long as the underlaying (fixed-width) function is indistinguishable (computationally) from a random one.

So the real reason we don't usualy use a "transformation", is that - It's not usually efficient.

Quote from the mail response.

  The reason that the sponge construction is mostly instantiated with
  permutations (Keccak, Xoodyak, Spongent, etc.) is that we - as a
  cryptographic community - have a method to build efficient permutations
  that seem to give rise to secure sponge functions but not to build
  efficient transformations that do the same and the invertibility of the
  permutation does not hurt as far as the indifferentiability and
  indinguishability bounds are concerned. ...

This is true, the round functions in Feistel-network block ciphers such as DES and SM4 aren't optimal efficiency-wise, especially when compared to constructs such as ARX (add-rotate-xor such as that in ChaCha20), and bitwise-and-shift operations (such as those in Gimli, Keccak, NORX).

To conclude:

  ... We actually build a permutation
  by iterating a simple round function that does mixing, nonlinearity and
  shuffling. Sponges have been built with a transformation that is not a
  permutation, like Gluon, but that was no great success in my opinion.


Why is SHA2 used for file verification if it's susceptible to length extension attacks? Am I misunderstanding length extension attacks, or is there some different reason, or is it really a bad idea to use SHA2 for file verification?

If the answer is that it's really a bad idea, would removing the last 4 bytes be advisable since now the chances of the attack succeeding will be around one in 4 million, and we will have remaining, in the case of SHA512, 480 bits of security?

The use of a hash function for verifying integrity of a file is not impacted by length extension attacks. The setup is the following:

You have a file $m$.
There is a "guaranteed" source for $h(m)$, with $h$ being a hash function. (For instance, you can get $h(m)$ from an HTTPS Web site with verified provenance.)
You recompute $h(m)$ and look for a match.

To make an undetected alteration of the file, the attacker would have to find a message $m'$ distinct from $m$, and such that $h(m) = h(m')$. This would constitute a second-preimage attack. No such attack is currently known on any of the SHA-* functions. The "length extension attack" does not seem to help for second-preimage attacks.

It is interesting to note that the "length extension attack" does not contradict any of the classical properties expected from secure hash functions (i.e. resistance to collisions, preimages and second-preimages).


Can Elliptic curve Diffie–Hellman (ECDH) shared secret be used as a static encryption key? I have two parties:

Alice who has a static public key PA

Bob who has a static public key PB

A static shared secret (S) is computed with ECDH.

Encryption and MAC keys are computed with a key derivation function:  (KENC, KMAC) = KDF(S)

The two parties send messages to each other, encrypted and authenticated respectively using KENC and KMAC. The encrypted messages are also stored in this encrypted form.

My question: how secure is using these static derived keys (KENC and KMAC) in the long run if I want encryption and authenticity, but I do not care about forward secrecy.

This usage is theoretically sound assuming you do not desire Perfect Forward Secrecy, but will exacerbate attacks on the block cipher by providing potentially very many messages encrypted under the same key, and will exacerbate side channel attacks by repeatedly deriving the static secret (allowing many chances to catch small fragments and re-assemble).

Consider also that if users A and B have a static secret, then party C who obtains either A or B's key, can recover the shared secrets in both directions, and thus impersonate either party, to either party.

Edit: Another notable attack: party D, who does not have either key but can capture packets, can replay any message that A or B sent, and they can send it in either direction at any time, of course the keys will still be valid so the message will appear authentic. This can be just as effective as a full break in many cases.


Definition of the term "key" I've looked in many places (NIST, text books, online resources) and I cannot find an answer to the definition of the term "key" from a semantic point of view.

Is it the "key" to cipher-texts (i.e. like a door key to lock/unlock), or is the the "key" to the algorithm (i.e. a crucial factor to make it work, like a keystone)?

I was taught that it was the latter, but I cannot find proof either way. I can understand if the difference is too minor to discuss, but I was wondering if the original intent of the term is known.

Edit:

To further clarify how I understand the semantics: because the key is required for the algorithm to function at all, the key is 'meant' for the algorithm (e.g. a keystone for an arch or a punch card for a IBM computer) the term 'key' is meant as an enabler for a process, not as a lock/unlocker for a secret. This is especially true because cryptographic keys can be used for algorithms that do not 'hide' or 'protect' data.

In the context of encryption schemes, the key is whatever piece of information the legitimate recipient of an encrypted message possesses, which allows him to decrypt the ciphertext efficiently. Hence, the key must be kept hidden from an attacker, since otherwise the attacker could decrypt efficiently just as the legitimate recipent does.


Can I do a forward secure half-round ephemeral-static ECDH? In the context of the project we are working on recently, we would like to enable users to "leave a message" to someone on the Internet securely. Our setting is as below:

ECC key pairs for open ID
AES-GCM as session for each message
Suppose Bob wants to leave a secret message to Alice, whose public key is known to the public.

Alice's key pair is (priv_a, pub_a)
Bob's key pair is (priv_b, pub_b)
Bob generates an ephemeral ECC key pair (epriv_b, epub_b)
Bob computes the shared secret of epriv_b and pub_a
Bob derives an AES-GCM key from the shared secret and creates (epub_b, sig of epub_b using priv_b, encrypted message using AES-GCM key) as M
Bob leaves this message somewhere (could either be public or private) so that Alice could see it
Alice performs the same process to derive the AES-GCM key to decrypt the message and verify Bob

In this scenario, the forward secrecy is not guaranteed. I am curious if we can possibly ensure the forward secrecy under this scenario with only half round of communication (one-sided). If not, is there any alternative that I can adopt to accomplish the goal? Any direction or hint is appreciated.

I am curious if we can possibly ensure the forward secrecy under this scenario with only one round of communication.

I do not believe so; the protocol can be summarized as:

Alice publishes her long term key
Bob does some work (without having Alice do anything)
Alice does some work, and retrieves the message

If, anywhere between points 1 and 2, Alice's state was copied, then the copy of Alice's state would be able to perform step 3 just as well as Alice did, and so you don't get PFS.

Also, terminology correction: you asked whether this can be done with only one round of communication; actually, it can, by having Alice send a message at the start of step 2.  Obviously, this doesn't work for your project; what you need is actually a 'half round' exchange.


Choice of MAC and handling it correctly I have recently learned that Encrypt-then-MAC is recommended when using symmetric encryption.

I have two closely related questions related to that, which is why I am posting them as one:

Looking at the different kinds of available MACs (UMAC, HMAC, etc.), does it matter which one I use? Meaning: does the choice of MAC depend on the cipher, or the mode of the cipher, or anything else? Or is it more a matter of personal preference which kind of MAC I use?
Am I assuming correctly that I can transmit a MAC together with the related ciphertext? Meaning: is it safe to append the MAC to the ciphertext upon transmission, or is there another way I should prefer (separate transport over secure channel, or something like that)?

There are various factors that go into choosing a MAC algorithm, for example: Use cases for CMAC vs. HMAC? documents CMAC vs. HMAC; I think HMAC is a reasonable default choice though (supported by Colin Percival: http://www.daemonology.net/blog/2009-06-11-cryptographic-right-answers.html).
Yes, the MAC can be transmitted alongside the ciphertext, one thing to remember to do when verifying the MAC is to use a constant time comparison: http://codahale.com/a-lesson-in-timing-attacks/


Are Feistel ciphers subject to the birthday bound? This paper seems to be saying that a balanced Feistel cipher can be broken when an adversary has $2^{0.5 \cdot n}$ pairs of plaintext and cipher text blocks where $n$ is the block size in bits. Is this true?

No. You need to focus on the stated assumptions in the paper.

It is saying that you need 6 or more rounds to get high security against attacks with no more than $2^{n}$ plaintext ciphertext pairs for a classical (balanced) feistel cipher with truly randomly chosen round functions. This is of course an idealized model for a feistel cipher.

To test your understanding the sentence "In this paper we will show that 5-round random Feistel schemes resist all CPA-2 attacks when m ≪ 2n and that 6-round random Feistel schemes resist all CPCA-2 attacks when m ≪ 2n." is the crucial statement.


Viability of an "Unconventional" Hashing Scheme? I am playing around with the following hashing scheme:

Start with a domain string (same for all users),
Allow every user to mutate it in any way defining their own custom replacement rules,
Append the user ID to the result of the above mutation,
Allow the user to choose their own "work factor" for PBKDF2-HMAC-SHA256, and use the above "salt" to hash their secret.

In the worst case, if the replacement scheme is an identity mapping, and if the user ID is empty, the salt will end up the same and this scheme will suffer from "salt clustering". If the user also did not customize their work factor, this would be a weak scheme allowing for a rainbow table attack for all users for a given domain.

However, let us assume that all three elements have sufficient variability:

the replacement scheme is arbitrarily complex,
the user ID exists,
the work factor is variable

In this case, how does the security of the resulting hash database for a given domain stack up against the pedantic case of choosing a salt using a CSPRNG, and hash the secret using a fixed work factor? Are their any obvious "gotchas"?

Edit: The "setup" is intended to be a one-time cost, to be used across domains, i.e., the replacement scheme will be used for multiple domains.

Edit Redux: From the discussion below, it basically boils down to the fact that as long as the input is deterministic and so is the ruleset - which in most cases will be a naive substitution - a precomputation of rainbow tables for an "intelligent" search space on the salt is possible. I will change my design accordingly.

It is too likely the input mutation reduces the search space too much as most people will input heavily lossy mutations. I know better. 99% of people don't know better.

Even the simple case of {"at"->"@", "what"->"#"} which I see as the kind of thing people will be loading, is a bad idea.


The meaning of formal and semi-formal in cryptography The question is about "formal" analysis, proofs, etc... What is a correct definition of a formal proof, or a formal analysis? Is there a good way and a bad way to formally prove something. What is the meaning of a a "semi-formal" proof, "semi-formal" argument.

You may want to check the answers to this question. As the question (and answers) point out, it is not rare to find people use "formal proof" to refer to proofs generated using computer-aided means.

However, as some comments to your question also point out, a "formal" proof of something strictly means a mathematical proof showing that all the claimed (security) properties are met. This can be done using computer-aided tools, but not necessarily. The term provable cryptography refers to a major area in cryptography which deals with the main techniques to create such proofs (not necessarily -and not usually- computer-aided tools). See, for instance, this entry in the Wikipedia for some further insight and references.

About "semi-formal" proofs: I guess that it refers to proofs that do not go down to the full detail, and just set out the overall approach and leave some (or all) parts as sketches. This means that while they may overlook some things, such "semi-formal" proofs point towards the right direction to build a formal proof.


Two salts, One password If I have two different MD5 password hashes with two different salts (the salts are known), is there any way to cryptographically deduce if the two passwords match? Other than brute force password cracking, that is.

No, if it is possible then it defeats the purpose of using salts. For example, one can build one rainbow table, mapping each possible password together with a fixed salt value to a hash value. Then given another salt value and password hash, one can find the password in the table if what you asked is possible.


Is it safe to generate ECDSA keys from the hash of the previous, over and over again? I have memorized a very long and secure passphrase, that when hashed with sha256, I can use the result as an ECDSA private key, and use it as a brain-address for Bitcoin.

Now I need more bitcoin addresses, and instead of memorizing a new long and secure passphrase, I am thinking about just hashing the previous hash, over and over again to create new keys.

So I can build a simple software to which I type the passphrase and I tell him I want the key of the address number 58, so it just has to sha256 the passphrase 58 times to get that key.

If the greatest hacker ever had for example the first 500 bitcoin addresses that were generated with my passphrase, and if that hacker knew how those private keys where generated, would he have any chance to hack this system?

I am pretty sure he wouldn't but I want to make sure, because this is for a project at my job.

This approach will work, but there's another approach I want you to suggest.

As for why it's secure (or better the ways to attack):

Break the elliptic curve discrete logarithm problem. If you can do this you can just grab the first address out of your addresses, solve for the private key and derive all subsequent ones. This is generally considered infeasible.
Brute-force your passphrase. This is impossible as you describe it as "very long and secure".

Now for the alternative approach:

Don't use iterated hashing on your password for the ECDSA key derival. Use HKDF-extract on your password and then derive each indexed key using HKDF-expand which will allow you to supply context-information. You could simply use "1", "2","3",... as context info here. Use the derived values as ECDSA private keys.

The advantages are:

Independent keys. Compromise of one private key doesn't imply compromise of all subsequent private keys, because they are all independent.
Higher speed. If you only want to access your account number 500, you'd have to iterate your hash function 500 times (which may take a moment). With HKDF you get this at a few HMAC calls independently of the index.
More security. If you use HKDF you don't need to store / buffer 499 intermediate private keys on your machine, whereas with iterated hashing you'd have to (although you still have to store the master password).


Fiat-Shamir vs Common Reference String to make NIZK I was introduced to NIZK from the notion of CRS: since we have a trusted CRS, then a prover can simulate a challenge by querying the CRS.

Similarly, the prover can simulate the challenge of a verifier by using the Fiat-Shamir heuristic.

Can someone explain if there is any relation between the two?
Are they two different methods or very similar?
Can we replace the oracle with a PRF and a CRS?

Sorry for the confusion, if someone can clarify the two models and also give me pointers would be really appreciated.

Since there are no answers here yet, I'll write down my own opinion.

The Fiat-Shamir heuristic for augmenting Sigma-protocols (or possibly any 3-move honest-verifier ZKPoK?) works as follows: For the problem statement $X$ and first prover message $A$, the prover self-generates the challenge $e = H(X,A)$and uses it to generate its final response $z$. Note that these proofs can be replayed.
In Damgard's paper “Efficient Concurrent Zero-Knowledge in the Auxiliary String Model” the Common Reference String model is used to generate a trapdoor commitment scheme, enabling the verifier to simulate a proof and thus guaranteeing zero-knowledge. In this setting, since the prover still actively participates in the protocol and Special Soundness is assumed, the prover cannot cheat.

To me it seems that your conjecture is true. Given a collision-resistant hash function $H$ (a criterion I think a PRF satisfies), digesting $A$ and the common reference string together should derive a ZKPoK out of a Sigma Protocol. But the thing is, that string should only be unique, and it is solely in the interest of the verifier that it be so. Therefore even a malicious verifier can be trusted to provide it properly, and the overhead of a CRS setup having to generate unique strings can be avoided.


How is encryption broken today? There are often articles in the news that state that a certain country or hacker has been able to decrypt/hack highly protected systems: Some examples are the Lockheed Martin RQ-170 Sentinel that was downed in Iran and later said to be partly reverse engineered by China or the Snowden files that might have been hacked by Russia and China. There are plenty of other examples.

My question is now the following: How could this have been done considering the fact that a brute-force method would certainly not work because of the encryption strength and leaving other non-technical aspects like spies etc. out of consideration.

Modern encryption can be broken in practice even when the algorithms are theoretically secure. There are a variety of ways this can happen:

Side channel analysis could have played a part.

The accepted answer to the linked question is excellent and provides some very good examples.

Exploitation of implementation bugs could have played a part.
Malware presence on the machine more or less negates any benefits of encryption, as advanced enough malware can simply watch and even modify anything/everything that you do.
Users may simply be coerced into surrendering the password which is used to derive their encryption keys.

More about Side Channels

  General classes of side channel attack include:

  Cache attack — attacks based on attacker's ability to monitor cache accesses made by the victim in a shared physical system as in virtualized environment or a type of cloud service.
  Timing attack — attacks based on measuring how much time various computations take to perform.
  Power-monitoring attack — attacks that make use of varying power consumption by the hardware during computation.
  Electromagnetic attack — attacks based on leaked electromagnetic radiation, which can directly provide plaintexts and other information. Such measurements can be used to infer cryptographic keys using techniques equivalent to those in power analysis or can be used in non-cryptographic attacks, e.g. TEMPEST (aka van Eck phreaking or radiation monitoring) attacks.
  Acoustic cryptanalysis — attacks that exploit sound produced during a computation (rather like power analysis).
  Differential fault analysis — in which secrets are discovered by introducing faults in a computation.
  Data remanence — in which sensitive data are read after supposedly having been deleted.
  Row hammer — in which off-limits memory can be changed by accessing adjacent memory.
  Optical - in which secrets and sensitive data can be read by visual recording using a high resolution camera, or other devices that have such capabilities.


Hashing entropy to generate 256bit key? I have a 256bit fully random entropy source from dices, which is probably not cryptographically secure. I have read that it's customary to take the hash of the entropy source in order to generate a safe key.

My goal is to generate a 256bit secure key for cryptographic purposes.

Somebody suggested to me to take the SHA-256 of the entropy source, but wouldn't that cut the entropy in half,as the SHA-256 actually has only 128 bit entropy? So shouldn't I use SHA-512.
Shouldn't I use the SHA3 variant instead of SHA2 as it's newer and more recommended?
Would the resulting key be truly cryptographically secure, unbiased, and uniform?
What happens if I cram more entropy into the hash function, say 270 bits.
What happens if the hash function's output is of more bits than the entropy source (hash 256 bits, but entropy source only 250 bits), what happens then to the security of the key?

I have a 256bit fully random entropy source from dices, which is probably not cryptographically secure.

If you roll enough dice, the rolls are fair, and no adversary can monitor them, it is cryptographically secure.  The reason is simple: an adversary who can't snoop on the dice rolls can't guess the results in any reasonable amount of time either.

You should concatenate (not add!) the results in the exact order you get them.  Each roll of a fair six-sided die has $log_2(6) = 2.58$ bits of entropy, so you need 100 rolls from six-sided dice to get to the 256-bit mark.

The more complex case comes when the dice rolls aren't fair:

The dice are unbalanced, so that one side is heavier than the others, and thus the side opposite to that one is disproportionately likely.  (Casinos use special dice designed to be more balanced than ordinary dice.)
The dice are rolled in a way that doesn't really randomize the results.  (Shaking the dice vigorously in a dice cup is said to improve the fairness of rolls.)

In the case of an unbalanced dice, imagine for the sake of argument that a six is the most likely outcome, and the probability of rolling it is not 1/6 ($16.\overline{6}\%$), but rather 17/100 ($17\%$).  Then each roll has a min-entropy of $-log_2(17/100) = 2.556$ bits, so 100 rolls give you $255.6$ bits of entropy—just short of 256 bits.

In such cases you might need more than 100 dice rolls to get to a full 256 bits of entropy.  Or alternatively and much more practically, you could just convince yourself that the 100 dice rolls, even if somewhat unfair, are actually way more than enough to provide adequate security.  You almost certainly don't need 256 bits of entropy anyway. Why not just settle for about 128 bits?  Won't you get bored rolling 100 dice?  Be practical!

  I have read that it's customary to take the hash of the entropy source in order to generate a safe key.

What you need to do is encode the outcome of the rolls into a 256-bit string so that none of the possible 256-bit strings is significantly likelier than the others.  Hashing a string with the results is a convenient way of achieving that.

  Somebody suggested to me to take the SHA-256 of the entropy source, but wouldn't that cut the entropy in half,as the SHA-256 actually has only 128 bit entropy?

Hash functions don't have "entropy"—the result is determined by the input, so the result of the hash function can never be more unpredictable than the input.  An attacker who has a technique for guessing the input to the hash can use the same technique to guess the output.

That 128-bit security number you allude to is the collision resistance—how much effort it takes an attacker to find two inputs of the attacker's choice that produce the same output.  That is not relevant here because your scenario is different: you're choosing the input to the hash function, and you're showing neither the input nor the output to the attacker.

Intuitively, what the output size of the hash function does here is put an upper limit on the difficulty of guessing the result (and thus the entropy of your hashed output):

If your dice roll input has fewer than 256 bits of entropy, the quickest path for the attacker is to try and guess your dice roll results and calculate the SHA-256 result for each guess.  So in this case the output has exactly as much entropy as the dice rolls.
If the dice rolls have more than 256 bits of entropy, the quickest path for the attacker is to try and test all the possible SHA-256 outputs, without bothering to consider which dice roll inputs produce which outputs. This means that in this case the output can't have more than 256 bits of entropy.

This also answers your questions of "What happens if I cram more entropy into the hash function, say 270 bits" and "What happens if the hash function's output is of more bits than the entropy source (hash 256 bits, but entropy source only 250 bits), what happens then to the security of the key?"

  Shouldn't I use the SHA3 variant instead of SHA2 as it's newer and more recommended?

It is extremely unlikely to matter in practice.


Are there hash algorithms with variable length output? I understand that for example MD5 produces a 128 bit hash value from a given text of variable size. My question is if there is a hash-like algorithm that will produce a hash value where one can specify the length of the outcome? So one would specify that that given any input the hash value (output) should be say 1000 bits.

For example, I would like to produce a hash value of the same length as the input. One way that I had thought of doing this would be to just encrypt the input somehow, but this would probably be easy to break, since one would just decrypt.

Another way I had thought about would be to divide the input up into say 128 bit chunks and then do MD5 (or some other hash) on each part and then just create one long string with the hashes of all the strings. However, I can see that a change in the input in one byte only would change 128 bits of the output.

Sure.  If you want a $b$-bit hash of the message $m$, then use the first $b$ bits of AES-CTR(SHA256($m$)).  That'll do the trick.

In other words, compute SHA256($m$) and treat the resulting 256-bit string as a 256-bit AES key.  Next, use AES in counter mode (with this key) to generate an unending stream of pseudorandom bits.  Take the first $b$ bits from this stream, and call it your hash.  (Make sure you don't treat the IV as part of this stream, as the IV won't be pseudorandom.  You may need to manually remove the IV first before taking the first $b$ bits.)

Security. This should be secure as long as $b \ge 160$ or so.  In particular, a collision attack is expected to take about $2^{\min(b,256)/2}$ steps of computation, given our current knowledge of AES and SHA256.  So, as long as you don't choose a value of $b$ that is too small, you should be good.  Choosing a value of $b$ larger than 256 does not give you greater security against collisions, but that's irrelevant: the level of security will already be way more than enough for any reasonable application, so you're good.


Monotonic Access Structure I got confused with the monotonic access structure definition.

Following definition is one of the answers to the following question:

What are monotonic and non monotonic access structures in ABE ?

Let $\{1,2,...,n\}$ be a set of indices. An access structure is a collection $\mathbb{A}$ of non-empty subsets of $\{1,2,3,...,n\}$. We say a collection (or an access structure) $\mathbb{A} \subseteq 2^{\{1,2,...,n\}}$ is monotonic if for any $B,C \in 2^{\{1,2,...,n\}}$, if $B \in \mathbb{A}$ and $B \subseteq C$ then $C \in \mathbb{A}$.

According to the above definition, every access structure $\mathbb{A}$ which not include $\{1,2,3,...,n\}$ is not monotonic!, because every arbitrary $B \in 2^{\{1,2,...,n\}}$ always is subset of ${\{1,2,...,n\} }$

Could you please clarify what I am going wrong?

The access structure itself need not be non-empty, so the universe doesn't have to be in the structure. Of course, any non-empty access structure will have $\{1,2,\dots,n\}$ as an element.

In the context of ABE, it suffices to consider monotone access structures if the scheme supports an expressive policy set, because any subset $\mathbb{B}$ of $2^{\{1,2,\dots,n\}}$ (i.e., any not necessarily monotone access structure of universe $\{1,2,\dots,n\}$) can be encoded as a monotone access structure $\mathbb{A}$ of the universe $\{\pm1,\pm2,\dots,\pm n\}$ as follows:
$$\begin{aligned}\mathbb{A}'&{}=\Bigl\{{\{i\,|\,i\in X\}\cup\{-j\,|\,j\notin X\}}\,\Big|\,X\in\mathbb{B}\Bigr\},\\\mathbb{A}&{}=\Bigl\{A\,\Big|\,\mathbb{A}'\ni A'\subseteq A\subseteq\{\pm1,\pm 2,\dots,\pm n\}\Bigr\}.\end{aligned}$$
In English, this means you prepare positive/negative literals for every member of $\{1,2,\dots,n\}$, then encode any subset of it by explicitly putting negative literals for non-members into it, which gives you $\mathbb{A}'$. Then you take the smallest monotone access structure $\mathbb{A}$ containing $\mathbb{A}'$.

Monotone access structure gives rise to secret-sharing schemes, which are an important ingredient in many ABE constructions. Note that secret-sharing schemes can only handle monotone access structures, because gaining more shares only makes reconstruction easier.


Winternitz hash based signature signing and verification In Winternitz hash based signature

There are two functions
$f: \{0,1\}^n \to \{0,1 \}^n$, a one way function
and $g: \{0,1\}^* \to \{0,1 \}^n$, cryptographic hash function

Key Generation steps

First $w$ is selected, where $w$ is number of bits signed simultaneously.
The $t_1$ and $t_2$ is calculated as $t_1 = \lceil \frac{n}{w}\rceil$ and $t_2 = \lceil \frac{\lfloor log_2t_1\rfloor +1+w}{w}\rceil$, $t = t_1 + t_2$
Signature Key (Private key) is then chosen at random $X = (x_{t-1}, ..,x_0)\in \{0,1 \}^{n, t}$
Verification key (public key) $Y$ is calculated by applying $f$ function $2^{w} - 1$ times on each bit of $x_i$

Signing steps

Compute digest of message $d = g(M)$
Prepend minimum number of zero's to make length of $d$ divisible by $w$

My questions are

How is signature $\sigma$ computed? I am unable to understand from Post Quantum cryptography. Explanation with example would be helpful.

Why there is two functions $f$ and $g$, is there can be only one hashing function. What is the role of function $f$?

https://csrc.nist.gov/csrc/media/events/workshop-on-cryptography-for-emerging-technologies/documents/mcgrew-sigs.pdf

https://www.e-reading.club/bookreader.php/135832/Post_Quantum_Cryptography.pdf

How is signature $\sigma$ computed?

Well, you left a few steps out of your signing steps:

Signing steps

Compute digest of message $d = g(M)$
Prepend minimum number of zero's to make length of $d$ divisible by $w$

(Note: in practice, the length of $d$ is typically already divisible by $w$, and so this step usually doesn't do anything; in any case, $d$ will be $t_1$ digits long after this step)

Generate an "inverse checksum" of $d$; that is, treat $d$ as $t_1$ digits of length $w$ each $d_0, d_1, ..., d_{t_1 - 1}$, compute $k - \Sigma\  d_i$ for some constant $k \ge t_1 (w-1)$, and express that as the $t_2$ digits $d_{t_1}, d_{t_1 + 1 }, ..., d_{t_1 + t_2 -1}$

For each $d_i$, take $x_i$ and apply $f$ to it $d_i$ times

The result of these operations on the $t_1 + t_2$ digits are concatenated; that's your signature

You asked for an example, here's a toy one; let us assume that $w=2$ and $n = 4$.  Then:

We have $t_1 = 2$ and $t_2 = 2$

We compute $g(M)$ as 0111, which is $\{ 1, 3 \}$ as expressed as $w$-bit digits

We don't need to prepend any zeros, the length of $d$ is already a multiple of $w$

We generate our inverse checksum; we have $d_0 = 1$ and $d_1 = 3$; we'll use the minimal $k = 6$, and so we have $k - \Sigma \ d_i = 2$, which we'll encode as $d_2 = 0$ and $d_3 = 2$

We compute the Winternitz chain for $d_0$; $d_0 = 1$, and so this is $f(x_0)$; that's the first 2 bits of the signature.

We compute the Winternitz chain for $d_1$; $d_1 = 3$, and so this is $f(f(f(x_1)))$; that's the second 2 bits of the signature.

We compute the Winternitz chain for $d_2$; $d_2 = 0$, and so this is $x_2$ (that is, for digits of 0, we give out the private key value); that's the third 2 bits of the signature.

We compute the Winternitz chain for $d_3$; $d_3 = 2$, and so this is $f(f(x_3))$; that's the last 2 bits of the signature.

Why there is two functions $f$ and $g$, is there can be only one hashing function. What is the role of function $f$?

They, of course, perform different roles; $g$ hashes an arbitrary message down to $n$ bits; while $f$ is a one-way function that is used within the Winternitz chain itself.  They are usually (but not always) based on the same hash function; however how the hash function is used is typically optimized for each role separately.

Of course, in practice, we do a few refinements of the above scheme:

We actually use a different $f$ function for every iteration, and for every digit; that's to avoid multi-target attacks

Our public key really isn't $(t_1 + t_2)n$ bits long; typically, there's a final step that combines them into a single $n$ bit value.

Knowledge of these refinements is not necessary to understand Winternitz signatures; however you ought to be aware of them if you dig into a real usage.


Why is there no 'ECDSA' version of 'DHE-RSA-CHACHA20-POLY1305'? So I was just checking my TLS cipherlist and noticed that there was a 'DSS' / DSA / ECDSA version of every RSA cipher available, except for DHE-RSA-CHACHA20-POLY1305.

Why is that?

The original cipher suites involving ECDH and ECDSA were all introduced together in RFC 4492.  They corresponded to existing cipher suites:

\begin{equation}
\begin{array}{rcl}
  \text{DH_DSS} &\longmapsto& \text{ECDH_ECDSA} \\
  \text{DHE_DSS} &\longmapsto& \text{ECDHE_ECDSA} \\
  \text{DH_RSA} &\longmapsto& \text{ECDH_RSA} \\
  \text{DHE_RSA} &\longmapsto& \text{ECDHE_RSA} \\
  \text{DH_anon} &\longmapsto& \text{ECDH_anon}
\end{array}
\end{equation}

One might infer that the thinking was if you were going to take the plunge into the world of elliptic curves—recall in 2006 elliptic curve cryptography had (and to some extent still has) an undeserved reputation for being new and poorly understood in contrast to modular exponentiation systems in finite (quasi-)fields—then you might as well use ECDH key agreement, while you might keep your long-term RSA certificate because it was costly to buy a new one.  Doing it the other way around—buying an ECDSA certificate but using finite-field DH key agreement—would just be silly.

(Recall that this was also perhaps the heyday of the HTTPS certificate authority protection racket, before the browsers collectively imposed any semblance of regulation on it by the CAB Forum and long before Let's Encrypt rendered it obsolete.)

One might further infer that nobody bothered to break this pattern, because why would you want to do any more finite-field DH key agreement in this day and age anyway?


python secrets security evaluation The python library secrets gives a title as;

  "Secrets - Generate secure random numbers for managing secrets"

and makes a distinction from "random module" by

  In particularly, secrets should be used in preference to the default
  pseudo-random number generator in the random module, which is designed
  for modelling and simulation, not security or cryptography.

What are the methods the secret use?

And, are there any security evaluation of python's secret library?

Did you RTFM?  It's right in the link you provided above: "The secrets module provides access to the most secure source of randomness that your operating system provides."

If you trace is back it uses os.urandom() which "... returns random bytes from an OS-specific randomness source. The returned data should be unpredictable enough for cryptographic applications, though its exact quality depends on the OS implementation. On a UNIX-like system this will query /dev/urandom, and on Windows it will use CryptGenRandom()."


Is there a practical zero-knowledge proof for this special discrete log equation? We have a multiplicative cyclic group $G$ with generators $g$ and $h$, as in El Gamal.  Assume $G$ is a subgroup of $(\mathbb{Z}/n\mathbb{Z})^*$.  There are two parties, Alice and Bob:

Alice knows:  $g$, $h$, $x_1$, $x_2$ and $(a,b,c)$,
Bob knows: $g$, $h$ and $(a,b,c)$.

Can Alice prove to Bob in zero knowledge that she knows $x_1$ and $x_2$ such that $(a,b,c) = (g^{x_1} , x_2·(h^{x_1}), h^{x_2})$?

This proof must be practical and non-interactive.

Let $\#G$ denote the number of elements in the group. In your particular case, $\#G = \varphi{}(n)$ (and even $\#G = n-1$ if $n$ is prime). Let $\xleftarrow{\$}$ denote a uniformly random sampling from a finite set of elements. Furthermore, $\mathbb{Z}_m$ denotes the set of non-negative integers smaller than $m$ and $\stackrel{?}{=}$ denotes a equality test between two values to be performed by the Verifier. The Verifier accepts if and only if all such equalities hold.

Public knowledge: $g, h, a, b, c$

Claim: knowledge of $x_1, x_2$ such that $(a,b,c) = (g^{x_1},x_2h^{x_1},h^{x_2})$

Interactive proof:

$\begin{matrix}Prover & & Verifier\\
v,s,s',s'' \xleftarrow{\$} \mathbb{Z}_{\#G} & & \\
 & \xrightarrow{\begin{matrix}(g^s),(h^{s'}),(h^{x_1s''}),(x_2^{s''}),(x_2h^{x_1})^v\end{matrix}} & & \\
& & k \xleftarrow{\$} \mathbb{Z}_{\#G} \\
& \xleftarrow{k} & \\
r \xleftarrow{} x_1 + ks \mod \#G & & \\
r' \xleftarrow{} x_2 + ks' \mod \#G & & \\
r'' \xleftarrow{} v + ks'' \mod \#G & & \\
& \xrightarrow{r,r',r''} & \\
& & g^r \stackrel{?}{=} a(g^s)^k \\
& & h^{r'} \stackrel{?}{=} c(h^{s'})^k \\
& & b^{r''} \stackrel{?}{=} ((x_2^{s''})(h^{x_1s''}))^k(x_2h^{x_1})^v\end{matrix}$

The proof can easily be made non-interactive by applying the Fiat-Shamir heuristic, i.e.: $k = \mathcal{H}(g,h,a,b,c,\ldots)$ where $\mathcal{H}$ is a suitable hash function which is applied to the input of the protocol and (optionally) some extra sources for randomness such as the time or the Prover's first message.

Theorem 1. This interactive proof is complete, i.e.: if the claim is correct, the Verifier will accept.

Proof. Proof by construction.

$g^r = g^{x_1+ks} = a(g^{s})^k$

$h^{r'} = g^{x_2+k{s'}} = c(h^{s'})^k$

$b^{r''} = (x_2h^{x_1})^{r''} = (x_2h^{x_1})^{v + ks''} = ((x_2^{s''})(h^{x_1s''}))^k(x_2h^{x_1})^v$ $\square$

Theorem 2. This interactive proof satisfies the special soundness property, i.e.: only if the claim is true will the Verifier accept (and, moreover, any two accepting transcripts of this proof applied to the same claim and starting with the same initial message will leak the witnesses $x_1$ and $x_2$).

Proof. We prove the "moreover" part of the theorem as it implies regular soundness. Given two transcripts $T_1$ and $T_2$, we can first compute $s$ from $T_1.r - T_2.r = (T_1.k - T_2.k)s$ and then compute $x_1$. The same goes for $r', s'$ and $x_2$.

Of course, if $T_1.r = T_2.r$ and $T_1.r' = T_2.r'$, then this does not leak the witnesses per se. However, in this case $T_1$ can only be different from $T_2$ if $T_1.r'' \ne T_2.r''$ from which we can calculate $v$ and $s''$. The latter value allows us to calculate the witness $x_2 = (x_2^{s''})^{s''^{-1}}$. $\square$

Theorem 3. This interactive proof is special honest-verifier zero-knowledge.

Proof. There exists a simulator algorithm $\mathcal{S}$ which takes as input the claim $(g,h,a,b,c)$ and a challenge $k$ and outputs a transcript $S$ of the interactive proof which is indistinguishable from the transcript $T$ of an authentic interaction proving the same claim.

The simulator $\mathcal{S}$ generates a valid conversation $(((g^s),(h^{s'}),(h^{x_1s''}),(x_2^{s''}),(x_2h^{x_1})^v),(k),(r,r',r''))$. Let the elements of this conversation represent variables which are to be assigned a definite value. The simulator $\mathcal{S}$ does this as follows.

$ \begin{matrix}r,r',r'' \xleftarrow{\$} \mathbb{Z}_{\#G} \\
 v \xleftarrow{\$} \mathbb{Z}_{\#G} \\
 (x_2h^{x_1})^v \xleftarrow{} b^v \\
 (g^s) \xleftarrow{} (g^ra^{-1})^{k^{-1}} \\
 (h^{s'}) \xleftarrow{} (h^{r'}c^{-1})^{k^{-1}} \\
 (x_2^{s''}) \xleftarrow{\$} G \\
 (h^{x_1s''}) \xleftarrow{} (b^{r''}b^{-v})^{k^{-1}}(x_2^{s''})^{-1} \end{matrix}$

There cannot exist a distinguisher $\mathcal{D}$ who can distinguish between an authentic transcript $T$ and a simulated transcript $S$. The distributions of $T$ and of $S$ are identical. $\square$


Secure instant messaging protocol and implementation for an anonymous end-to-end chat? all is said in the title but I will go further.
First question :
I searched here and I found Tox to be the most powerful protocol. It uses Curve25519, XSalsa20 and Poly1305. They seem to be good algorithm but I think I will replace XSalsa20 for a ChaCha20-Poly1305 combination.
What are you think about that ?
Second question :
For the implementation this is my first thougth :
A ask for a secure communication to the Server which register the channel on his DataBase and cipher it with A's symmetric key. When B ask to connect on the channel, the server will send the request to A with his public key, A will cipher symmetric key of the channel (unknown by the server) and send to B back. The server will finally add B to the DataBase of the channel. If B want to send a message he need to cipher it with one of the symmetrical key and send the coded text to the server wich will decipher the DataBase with the key and send to every ip addresses. A will decode with the other symmetric key.
I know it's unclear, if you have any questions feel free to ask them, I want to know if you got better idea. The problem of my system is that the server will keep ip addresses of the channel's owner and the user (while he connect to the server) until all the users are connected. But I don't think it's possible to do it without that.

I searched here and I found Tox to be the most powerful protocol.

The reason, why I'd advise against Tox and for the Signal Protocol is not a one of features.

Tox has seen not much review, especially not from cryptographers. The core library is also still in alpha. In fact, an audit is still an open issue for them on GitHub, so I don't have too much trust in their security for now.

The Signal Protocol on the other hand, has very wide-spread deployment (in apps like Signal, WhatsApp, Google Allo and Facebook Messenger) and thus has seen a lot of scrutiny. The creators also have conducted security audits of their software and academics have given it a lot of attention.

  What are you think about that ?

From a purely cryptographical stand point this is totally fine, except maybe that ChaCha hasn't yet seen as much scrutiny as Salsa20 (and XSalsa20) have yet. But ChaCha is considered to be just as secure.
However, doing this will make you incompatible with all other existing implementations of Tox which will make it "harder" to integrate support for your product into other, potentially harming adoption rates.
Secondly, I assume you'd use the Tox-core library and changing stuff in those libraries is always dangerous and because of the change you may introduce a new vulnerability.

  A ask for a secure communication to the Server [...]

You don't need a centralized server, that's one of the points going for Tox. Everything can be done peer-to-peer (mostly).

As for your actual protocol there are a few issues:

From what I can tell, it's trivial for the server to serve bad public keys and MitM attack connections (this also depends on whether the UI will allow to verify public keys though)
IP adresses can change over time, not ideal for a chat application (depending on how long they need to stay valid)
Depending on how connection establishment works, users sitting behind drop-all firewalls and NAT routers may also have problems
The server learns the social structures of the users (eg who groups up with whom)
You lack a threat model (e.g. what do you want to achieve? Who is considered a threat?)

Most of these issues can be mitigated server-side using software (like don't store IPs, don't store grouping, keep the incoming connections alive) only the mitm attack mitigation would need client-side action.

And of course this quick check by me doesn't replace a full review by a professional cryptographer.


Non primitive lfsr sequence Given a non-primitive LFSR sequence (i.e number of states is less than $2^n - 1$); how do we find out the the characteristic polynomial? Will Berlekamp-Massey algorithm work in this case?

for example; for the following sequence-

[1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1]

the repetition period is $105$. Applying the Berlekamp-Massey algorithm returns

$X^7 + X^6 + X^5 + X^1 + 1$

Doing manually gives me a different answer.
Where am I going wrong?

EDIT

Adding what I did manually:

I found the primitive polynomials and took LCM to confirm the $Berlekamp-Massey$ output.

To check, I represented the polynomial as $11100011$ ; took the first seven bits of the sequence and did the $and$ operation with the polynomial. took the $xor$ of the output and appended that output to the initial 7 bits and continued. This is what I did to crosscheck the answer I received. It is here I went wrong probably.

A binary sequence of period $105$ will have characteristic polynomial
that is a divisor of $x^{105}-1$. Since $x^{105}-1$ has irreducible
factors of degrees $12, 4, 3$, and $1$, it is possible to have an LFSR
of length $4+3=7$ generate a sequence of period $105$, and that is
exactly what has happened here. Note that
$$x^7+x^6+x^5+x+1 = (x^3+x+1)(x^4+x^3+1)$$
where $x^3+x+1$ and $x^4+x^3+1$ are irreducible (in fact, primitive) polynomials of degrees
$3$ and $4$. Individually, the shorter LFSRs generate sequences of
periods $7$ and $15$: the "product" sequence has period
$\operatorname{lcm}(7,15)=105$.


Mapping the hash of message to a point of elliptic curve for signature Let the subgroup $G$ of elliptic curve constructed with point $P$ with prime order $q$ by $G=\langle P\rangle $. The $h(x)$ is a hash function. We want to map the hash of arbitrary message $m$ to a point in $G$ for use in the signature algorithm (such as BLS).
Why we don't use $k=h(m) \bmod q$ and then $S=kP$, whereas it is clear that the point $S$ is in $G$?
What is the flaw of this? security or efficiency?

That's insecure.
In BLS signatures: for private key $x$ and public key $X = xP$, the signature is computed as $T = xS$, and the verification checks if $e(T, P) = e(S, X)$, which works because:

$e(T, P) = e(xS, P) = e(xS, P) = e(S, P)^x$
$e(S,X) = e(S, xP) = e(S, P)^x$

If you know that $S = kP$, then you can forge a signature for a message with hash $k'$ from a signature of a message with hash $k$ by simply computing $T' = k'k^{-1}T$, which works because:

$T' = k'k^{-1}xS = k'k^{-1}xkP = xk'P = xS'$


SHA-256 is based on a Davies–Meyer compression function. Easy to find fixed-points are a known property of this construction.

A notable property of the Davies–Meyer construction is that even if the underlying block cipher is totally secure, it is possible to compute fixed points for the construction : for any $m$, one can find a value of $h$ such that $E_m(h) \oplus h = h$ : one just has to set $h = E_m^{-1}(0)$. This is a property that random functions certainly do not have. So far, no practical attack has been based on this property, but one should be aware of this "feature".
The fixed-points can be used in a second preimage attack (given a message m1, attacker finds another message m2 to satisfy hash(m1) = hash(m2) ) of Kelsey and Schneier for a $2^k$-message-block message in time $3 \cdot 2^{n/2+1}+2^{n-k+1}$. If the construction does not allow easy creation of fixed points (like Matyas–Meyer–Oseas or Miyaguchi–Preneel) then this attack can be done in $k \cdot 2^{n/2+1}+2^{n-k+1}$ time. Note that in both cases the complexity is above $2^{n/2}$ but below $2^n$ when messages are long and that when messages get shorter the complexity of the attack approaches $2^n$.

(from One-way compression function - wikipedia)
Thanks to Samuel Neves for pointing this out.


Equivalance Operator - Perfect Secrecy The equivalance operator is the inverse of the XOR operator, it's symmetric. Would this mean that it would also provide theoretical perfect secrecy just like XOR?

XOR

x ⊕ y = (x ∨ y ) ∧ ¬ (x ∧ y )

EQUIVALENCE

x ≡ y = ¬ (x ⊕ y)

There is no information leakage in theory if you just take the inverse of a perfectly symmetric function, it has to be perfect in both ways in theory.

What are you thoughts?

Actually, for any group operator $\odot$, we see that $x \odot y$ gives perfect security, assuming that $y$ is uniformly random over all possible group members.

The $\equiv$ operation is a group operation, with the group members being $\{0, 1\}$, with $1$ being the identity.  Hence, yes, it gives perfect security.


How do malware rely safely on ECDH algorithm to maintain secrecy of keys? In traditional malware (especially ransomware) using RSA approach, the public key may be hard-coded in the malware binary and is used to encrypt a symmetric key generated on the system. The symmetric key itself is used to encrypt user files.

Some new variants of malware are using ECDH instead of RSA. How is ECDH used in this context securely when malware analysts can reverse engineer the malware binary to find the curve and the parameters?

I have done the following research on this issue:

Read Wikipedia entry on ECDH
Watched a video in an attempt to comprehend it

So I understand the general concept of the logarithm problem where it is infeasible (computationally intensive) to find factors on the curve. But what I do not understand is this: if the curve and the pre-agreed parameters on the curve are hard-coded in the malware, can't malware analysts reverse engineer the malware binary to find the agreed upon curve and the parameters? Can this be then used to find the keys and beat the malware? If not, what is the "secret" that both malware developer and malware binary have access to (the two parties) but not the malware analyst who can reverse engineer the binary? For example, in the case of RSA, this secret is the private key which never leaves the attacker.

Quick summary.
Ransomware works by a public-key key encapsulation mechanism: pick a secret key $h$ and an encapsulation $\sigma$ of it for the malware operator's public key, so that only the malware operator can recover $h$ from $\sigma$ using their private key; then encrypt all the files using a symmetric cipher under the key $h$, erase $h$, and pay the malware operator ransom to get $h$ back from $\sigma$.

It's easy to build a public-key key encapsulation mechanism out of a public-key key agreement scheme such as ECDH with a long-term public key for the recipient: Generate a single-use anonymous key pair for the sender, combine the sender's private key with the recipient's public key to derive $h$, erase the sender's private key, and transmit the sender's public key as the encapsulation of $h$.  Using that as a subroutine, the malware then works just like it would with any public-key key encapsulation mechanism.

Details.
First, for reference, here's a way malware on the host can use a public RSA modulus $n$, say between $2^{2047}$ and $2^{2048}$, with secret factorization $n = pq$ known only to the malware operator.

Pick a nonnegative integer $x$ below $n$ uniformly at random using the host's random number generator, e.g. /dev/urandom on Unix or CryptGenRandom on Windows.
Compute and store $y = x^3 \bmod n$.
Compute $h = H(x)$, where $H\colon \mathbb Z/n\mathbb Z \to \{0,1\}^{256}$ is a random oracle.  E.g., you might instantiate $H$ with SHA-256 on the little-endian $\lceil\log_{256} n\rceil$-byte encoding of the least nonnegative residue of $x$.
Compute and store $c = \operatorname{AES-GCM}_h(\mathit{data})$, where $\mathit{data}$ is whatever important data are on the host's persistent storage that you're ransoming.
Erase $x$, $h$, and $\mathit{data}$.
When the hapless user pays the ransom, transmit $y$ and a proof of payment to the malware operator.

On receipt of $y$ and proof of payment, the malware operator can use secret knowledge of $p$ and $q$ to compute $x = y^d \bmod n$ where $d$ solves $3d \equiv 1 \pmod{\operatorname{lcm}(p - 1, q - 1)}$, and from there derive $h = H(x)$ for the luser to use to decrypt $c$ with AES-GCM.

The security of this scheme relies on the difficulty of computing cube roots of uniform random integers modulo $n$ without knowledge of the factorization of $n$.  There are some integers whose cube roots modulo $n$ are very easy to compute: the ones that are perfect cubes as integers in the first place, so that ordinary real number cube root algorithms can compute them.  But the vast majority of integers are not perfect cubes, so the probability that $y$ happens to be a perfect cube is negligible, and the cheapest algorithms we know to compute $x$ or $h$ given $y$ with nonnegligible probability work by factoring $n$, namely ECM and GNFS.

How does it work with ECDH?
Fix a standard public field $k$, say $\operatorname{GF}(2^{255} - 19)$.  Fix a standard public curve $E/k$, say $y^2 = x^3 + 486662 x^2 + x$.  Fix a standard public $k$-rational point $G \in E(k)$ of large prime order, say $G = \pm x^{-1}(9)$.  Fix a public $k$-rational point $P \in E(k)$ for which the malware operator knows a secret integer $s$ such that $$P = [s]G = \underbrace{G + G + \dots + G}_{\text{$s$ times}}.$$  Using these parameters, the malware on the host will:

Pick a nonnegative integer $t$ between $2^{254}$ and $2^{255}$ that is a multiple of 8, uniformly at random using the host's random number generator, e.g. /dev/urandom on Unix or CryptGenRandom on Windows.
Compute and store $Q = [t]G$.
Compute $h = H([t]P)$.
Compute and store $c = \operatorname{AES-GCM}_h(\mathit{data})$.
Erase $t$, $h$, and $\mathit{data}$.
When the hapless user pays the ransom, transmit $Q$ and a proof of payment to the malware operator.

On receipt of $Q$ and proof of payment, the malware operator can use secret knowledge of $s$ to compute $$[s]Q = [s\cdot t]G = [t\cdot s]G = [t]([s]G) = [t]P,$$ and from there derive $h = H([s]Q) = H([t]P)$ for the user to use to decrypt $c$ with AES-GCM.

This scheme is sometimes called ECIES.  The pair $(s, P)$ serves as the recipient's long-term key pair, while the pair $(t, Q)$ serves as the sender's single-use key pair, for public-key key agreement with an elliptic-curve Diffie–Hellman function.*  Choosing a single-use anonymous key pair like this turns a public-key key agreement scheme into a public-key key encapsulation mechanism.

The security of this scheme relies on the difficulty of computing discrete logarithms in the group $E(k)$.  The parameters are all public; all that the adversary—in this case, the hapless user who has been afflicted by ransomware, or the IT specialists they hire to recover their data without just paying the ransom—doesn't know are the secret integers $s$ and $t$, the AES-GCM key $h$, and the poor user’s data.

* The curve chosen, Curve25519, admits a fast algorithm to compute $x([s]G)$ given only $s$ and $x(G)$, which is why the Diffie–Hellman function is called X25519; we actually don't ever compute the $y$ coordinates or full points, just the $x$ coordinates above, but the notation got cumbersome when everything was written as $x(Q)$, $H(x([t]P))$, etc.


What Is The Number of Active S-boxes over 5 Rounds of Fides AE cipher? It is mention in the paper "
Fides: Lightweight Authenticated Cipher with Side-Channel Resistance for Constrained Hardware" , the number of active S-boxes of Fides cipher is 22 over 5 rounds but my result shows it is 25((9-3-1-3-9))using the same concept used in midori (same almost MDS matrix) to construct MILP model.

Q. Is anyone else got same results as mine? if not , is there any steps should i take to find the correct answer other than exhaustive search?

Your result is accurate: 25 active S-boxes is the best you can do in a 5-round trail. Here's an example for the 5-bit S-box variant, respecting the S-box constraints (and assuming I read the specification correctly):
$$
\begin{bmatrix}
\mathtt{19} & \mathtt{00} & \mathtt{1c} & \mathtt{1b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{1c} & \mathtt{00} & \mathtt{00} & \mathtt{1e} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{0c} & \mathtt{00} & \mathtt{1b} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{1b} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
$$
$$
\xrightarrow{SB}
\begin{bmatrix}
\mathtt{11} & \mathtt{00} & \mathtt{04} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{04} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
\xrightarrow{SR}
\begin{bmatrix}
\mathtt{11} & \mathtt{00} & \mathtt{04} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{11} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{04} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
\xrightarrow{MC}
\begin{bmatrix}
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{10} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
$$
$$
\xrightarrow{SB}
\begin{bmatrix}
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
\xrightarrow{SR}
\begin{bmatrix}
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
\xrightarrow{MC}
\begin{bmatrix}
\mathtt{00} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
$$
$$
\xrightarrow{SB}
\begin{bmatrix}
\mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
\xrightarrow{SR}
\begin{bmatrix}
\mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
\xrightarrow{MC}
\begin{bmatrix}
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{11} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
$$
$$
\xrightarrow{SB}
\begin{bmatrix}
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{08} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
\xrightarrow{SR}
\begin{bmatrix}
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{08} \\
\mathtt{00} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
\xrightarrow{MC}
\begin{bmatrix}
\mathtt{02} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{08} \\
\mathtt{00} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{08} \\
\mathtt{02} & \mathtt{00} & \mathtt{04} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{08} \\
\end{bmatrix}
$$
$$
\xrightarrow{SB}
\begin{bmatrix}
\mathtt{06} & \mathtt{00} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1d} \\
\mathtt{00} & \mathtt{00} & \mathtt{0c} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1b} \\
\mathtt{01} & \mathtt{00} & \mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\mathtt{03} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{03} \\
\end{bmatrix}
\xrightarrow{SR}
\begin{bmatrix}
\mathtt{06} & \mathtt{00} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1d} \\
\mathtt{00} & \mathtt{0c} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1b} & \mathtt{00} \\
\mathtt{02} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{01} & \mathtt{00} \\
\mathtt{03} & \mathtt{03} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} \\
\end{bmatrix}
\xrightarrow{MC}
\begin{bmatrix}
\mathtt{01} & \mathtt{0f} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1a} & \mathtt{00} \\
\mathtt{07} & \mathtt{03} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{01} & \mathtt{1d} \\
\mathtt{05} & \mathtt{0f} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1b} & \mathtt{1d} \\
\mathtt{04} & \mathtt{0c} & \mathtt{0b} & \mathtt{00} & \mathtt{00} & \mathtt{00} & \mathtt{1a} & \mathtt{1d} \\
\end{bmatrix}
$$

So where does the 22 come from? Well, modeling the S-box and the linear layer exactly can be costly. Instead, we can represent each nibble by a single bit and use the branch number $4$ of the almost-MDS layer to obtain a lower bound of active S-boxes. That is, for each column of the state in MixColumns, we have
$$
\begin{align*}
\sum (x_i + y_i) &\ge 4d \\
d &\ge x_i \\
d &\ge y_i \,,
\end{align*}
$$
for dummy variable $d$, input and output variables $x_i$ and $y_i$.
Because this is an almost-MDS matrix, we also need to additionally ensure that the output is nonzero if the input is (as described here):
$$
\begin{align*}
4\sum y_i - \sum x_i &\ge 0 \\
4\sum x_i - \sum y_i &\ge 0 \,.
\end{align*}
$$

However, when one does this, it results in the looser bound of $\ge 18$ active S-boxes over 5 rounds, not 22! So it remains a mystery where the 22 came from. The same observations also apply to 6 rounds, and possibly above.