texts: How can I calculate the time complexity of modular arithmetic?

texts:
I'm doing modular arithmetic in a Java program, and I want to calculate the time complexity of the individual operations.

$$ c= a · b \bmod n $$
$$ m = a^{-1} · b \bmod n $$

How do I get an approximation of the time complexity here, for example for 256-bit numbers?


texts: Key recovery when AES ECB is used for short but repeated messages

texts:
My question is based on the specification of the protocol LoRaWAN and especially on the part 6.2.5 Join-accept message.

It is said that the join-accept message is encrypted using AES ECB. This is (normally) a single message created like that:

aes128_decrypt(AppKey, AppNonce | NetID | DevAddr | RFU | RxDelay | CFList | MIC)

Imagine that an attacker can listen the communications. He doesn't know AppKey (obviously), AppNonce and of course the MIC. If the attacker can make the end device send plenty join-request messages and if the server always responds with a corresponding join-accept message, can the attacker gain knowledge of the AppKey using the flaws in AES ECB?

Disclaimer: sorry if I'm not clear, cryptography is not my speciality.


texts:
Is it possible to say that the most significant bit of an RSA private exponent is always 1? Wouldn't that weaken the key strength by exactly that one bit?

I refer to the paper "Timing Attack: What can be achieved by a powerful adversary?", p. 2, footnote 2.


texts: How does KECCAK operate on a state array filled with zeros?

texts:
Im trying to implement a sponge in Java. The state starts out as an empty 200 byte array of all zeros. In the KMAC samples document from NIST, the following happens:

(black line is a pdf page break)
The way Im reading this is that a state with a bunch of zeros was sent into KECCAK, and then a state with apparently random data was returned. Does SHA3/KECCAK turn empty data into random data? Am I asking the right questions here? Any help is appreciated.


texts: Difference between JWE encryption algorithm RSAES-PKCS1-v1_5 and RSAES OAEP

texts:
In the specifications of JWE (RFC7516) they specify the values for (asymmetrically) encrypting the symmetric key. In RFC7518 in section 4.1 they list the options, of which two are relevant for my case

alg = RSA1_5 (RSAES-PKCS1-v1_5)

or

alg = RSA-OAEP (RSAES OAEP using default parameters)

Both use RSA-keys of size 2048 at least. They come with a different recommendation (Recommended- and Recommended+, respectively). What are the main differences between these two algorithms for JWE, and is there a specific use of JWE that would prefer the one above the other?


texts: Is it safe to use XOR to encrypt data key using master key

texts: I am implementing a hierarchical key system with a randomly generated master key and many randomly generated data keys that should be encrypted using the master key. I am wondering what the best way to encrypt the data keys using the master key is. I am thinking that if I XOR the master key with the data key, that should be simple and safe. Is it? I couldn't find any documentation on this.


texts: Application of cryptographic hash functions which do not require collision resistance property

texts: I can not understand why collision resistance of a cryptographic hash function is not required for some applications. for example, if we store the trusted hash of a file or program, and later when we open the file and recalculate the hash and compare it to the trusted one, do we need it to be collision resistant?


texts: Homomorphic Public/Private Key Encryption Scheme for Floating Numbers

texts:
Is there any public/private homomorphic encryption scheme that directly works on floating numbers or vectors of floating numbers?

In our application, we want to find out if
$$v_1 \approx v_2, \qquad\text{or more precisely}\qquad \lVert v_1-v_2\mathbin\rVert < \epsilon,$$
with $v_1$ and $v_2$ being vectors with a fixed number of floating numbers.

An additional requirement for privacy protection is that we don't want the application to have access to the raw $v_1$.

So we suggest encrypting $v_1$,
$$w_1 = \mathit{Enc}(v_1, k_{\mathit{pub}})$$
and sending the encrypted version $w_1$ and the public key.

In the application, we can then check if
$$\mathit{Enc}(v_2, k_{\mathit{pub}})\approx w_1, \qquad\text{or more precisely}\qquad \lVert w_1-\mathit{Enc}(v_2, k_{\mathit{pub}})\rVert < \delta.$$

Is there an encryption scheme that supports this application?

Some references I found:

Fully Homomorphic Encryption for Point Numbers, Seiko Arita and
Shota Nakasato
Privacy-Preserving Oriented Floating-Point Number Fully Homomorphic Encryption Scheme, Shuangjie Bai et al.


texts: Vigenère cipher with sha512 and a little foresight turns to one-time pad. How safe can be?

texts:
I'm doing some exercises and of course I have read about the weaknesses of Vigenère cipher because it repeats the key. But what if I use a different hash every time? The hash of the "key + an increasing number".
In this example I encode a plaintext just with a sum of every single char (text[0] + pswhash[0] and so on). blocksize is 128 because I use sha512.

    f = open(filename)
    f2 = open(filename+'.encoded','w')
    x = 0
    while True:
        string = f.read(blocksize)
        if not string:
            break
        pswhash = sha512((psw+str(x)).encode('utf-8')).hexdigest()
        f2.write(encode(string, pswhash))
        x+=1
    f.close
    f2.close
    print("File encoded.")

how safe this could be?
Is this a real one-time pad?


texts:
I am writing a program which will use Chi-Square to determine which is the correct keyword for a ciphertext via Vigenère cipher.
I came across a website that describes the Chi-Square statistics in a rather simplistic manner and had also written some code to achieve my goals. However, the actual keyword does not seem to be the lowest chi-square value as according to the website. I'm not sure if the method as describe is correct or not.
Quoting the website:

Chi-squared Statistic
The Chi-squared Statistic is a measure of how similar two categorical probability distributions are. If the two distributions are identical, the chi-squared statistic is 0, if the distributions are very different, some higher number will result. The formula for the chi-squared statistic is:

where CA is the count (not the probability) of letter A, and EA is the expected count of letter A.
This page will describe the use of the chi-squared statistic for cryptanalysis. Ordinarily, statisticians use the chi-squared statistic for measuring the goodness of fit of data. Unlike statisticians, we make no assumptions about the distribution of our data, and draw no conclusions about the significance of the result. We simply use the method to suggest a possible decryption.
…

Would someone be able to provide some advice on this?


texts: Storing private keys directly in a keyring

texts:
Storing an RSA 2048-bit key directly in a keyring seems to work fine, and is advantageous because the application can be removed, broken, reinstalled and the key still works.

However, most apps seem to write out PCSS8 key files, and, instead, keep the random AES keys in the keyring for acccess.

Is there a good reason not to store the private keys directly in a properly encrypted user keyring?


texts: Why discrete logarithm modulo composite moduli not popular and not defined in standards?

texts:
The classical discrete logarithm problem is to find $x$ such that $g^x\equiv h\bmod p$ where $p$ is a prime and $g$ is generator of multiplicative group modulo $p$.
The demerit of this approach seems to be knowledge of $\lambda(p)$ where $\lambda$ is Carmichael Lambda function.
Supposing instead if we had $g^x\equiv h\bmod q$ where $q$ is composite $\lambda(q)$ is hidden since factorization is difficult.
One can still perform Diffie-Hellman at both Alice's and Bob's side since $(g^x)^y\bmod q$ can be computed without knowledge of $\lambda(q)$ and thus without knowing factorization of $q$.
Such a scheme includes factorization as an additional barrier in case discrete logarithm modulo primes is broken and so why is this not popular and defined in standards?
Note if discrete logarithm modulo primes is broken there is no way to use $q$ to be same length as $p$. We will only get smaller security if we use same length. $q$ has to be larger in length but the point is it cannot be prime. Perhaps $q$ is product of $\log p$ primes each of length $\log p$ bits.
Another phrasing of the problem is "Assuming an oracle solving the DLP modulo a prime, can we solve the DLP modulo a composite that's too large to factor?" as stated in a comment with each factor also reasonably large.


texts:
Keepass is a well known open-source password manager program, with plugin support. One of the offered plugin is a twofish encryption mode of operation in lieu of the build-in AES algorithm (http://keepass.info/plugins.html#twofishcipher).
Since I am fond of the xfish cipher family, I  looked at the source of that plugin before using it. That plugin ( http://gogogadgetscott.info/keepass/twofishcipher/) uses the C# twofish implementation from
http://www.codeproject.com/Articles/2593/A-C-implementation-of-the-Twofish-cipher in CBC mode.

In the C# source (file Twofish.cs) , the developer uses a all-zeros Initialization Vector (I am not sure how to relate to the Key zeroing):

    /// <summary>
    /// Generates a random initialization Vector (IV).
    /// </summary>
    public override void GenerateIV()
    {
        IV = new byte[16]{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0};
    }

    /// <summary>
    /// Generates a random Key. This is only really useful in testing scenarios.
    /// </summary>
    public override void GenerateKey()
    {
        Key = new byte[KeySize/8];

        // set the array to all 0 - implement a random key generation
                    // mechanism later probably based on PRNG
        for (int i=Key.GetLowerBound(0);i<Key.GetUpperBound(0);i++)
        {
            Key[i]=0;
        }
    }

Since Keepass is used to encrypt a dynamic set of password records with the same master password, I would assume that this implementation has some major security issues. I would like to solicit comments from the community on the above before I bring my concern up with the developer.

Note: In SUSE Linux 9.2 and below, they also used IV=[0] for their twofish CBC module:
"With SUSE LINUX 9.3 we switched from loop_fish2 to twofish as the encryption module. twofish together with cryptoloop is now the standard method for crypto partitions. We made that switch because twofish together with cryptoloop is more secure (cryptoloop uses the block number as the initialization vector, whereas loop_fish2 always uses zero) and is the standard solution for crypto partitions."


texts: Shuffling: Purpose and formal definition

texts:
To my understanding, shuffling means simply to permute the elements in vector $\mathbf{v}$ pseudorandomly, using a PRP $\pi (\mathrm{seed},\mathbf{v})$. A secure PRP should yield a permutation indistinguishable from a random one.
However, I'd still have 2 questions on this subject:

Is there a more formal definition to shuffling?

What is the purpose of shuffling? Is it simply to misalign power traces for differential power analysis attacks?


texts: Are zero knowledge proofs alternative private key encryption?

texts:
Are they the alternative to private keys. If I understand correctly, because of the increasing computational power in today's world, zero knowledge proofs are more safe than private keys ?
Are these two things connected in the way I understood it, or is my understanding a bit off?


texts: Is calculating HMAC from hashed input a good idea?

texts:
The original HMAC algorithm is as follows:

  H(K XOR opad || H(K XOR ipad || text))

What if text would replaced with H(text)? Will it weaken the HMAC algorithm?


texts: While reading a literature on signature schemes, I came across the concept of Existential Unforgeability of signature scheme against Adaptive Chosen Message Attack. Can anyone point me to the  paper where this notion was introduced first? Otherwise, may I ask for a paper/reference where the above-mentioned game is properly defined?


texts: Security proof for multi-message signature scheme

texts:
I have been going over the proof for security of a multi-message signature scheme and have a question. The part of the proof that I am unsure about is marked in yellow in the bellow snapshot. I do not understand why it is true.

Also, the attacker A' (as defined in the proof seen below) usually calls an oracle t times, but seeing as we have only one access to the oracle for A' does that mean A' has access to the multi-message scheme Sign() function? Does that not break the whole point of this? Can we not just call that Sign function on some message and be done with it?

This is the proof I have been presented with, (taken from here):


texts: How can one parallelize tasks in CTR-AES for maximum performance?

texts:
From what I have read it seems like one of the purported benefits of using CTR mode AES, is that it can be parallelized to a greater degree, or maybe more easily than the other block cipher modes, leading to performance gains?

In NIST SP800-38A §6.5 , it says:

  In both CTR encryption and CTR decryption, the forward cipher functions can be performed in parallel...

And this answer to “Decryption a chunk of file with AES”, if I understand correctly, suggests that basically you have one task do $$O_j=CIPH_K(T_j) \text{ for } j=1,2...\frac{n}{2}$$ with another task doing $$O_j=CIPH_K(T_j) \text{ for } j=\frac{n}{2},\frac{n}{2}+1...n$$ in parallel.

Is this what NIST SP800-38A, was referring to, something along these lines?
Or are there more or better ways to parallelize things?


texts:
Regardless of the KDF I will use, let's imagine that I have to generate two keys: one for authentication and the other for encryption (which will always remain on the device that generates it until logout). Of course, the key I use to encrypt and decrypt must always be the same.
I read some answers on this site that suggested generating a random salt for both keys and saving it with these (preferably separate). But there is a problem: when the user has to decrypt the data or authenticate himself, he will need this precise salt, which must be taken from the database. Since he isn't yet authenticated, how can I trust those who ask me for this salt? Because if I gave it to anyone who asks for it, it wouldn't make sense to use it.
Maybe I am wrong about some considerations since I am a newbie. If I am not mistaken in my assumptions, how can I resolve this stalemate? I have read that some recommend using the hash of the email or username as a salt in these situations. Is it a good practice?  Consider that anyone on the client-side can see what I do on the data.


texts: As far as I know the only disadvantage that XEX has when compared to CTR is that you need a block cipher/permutation while CTR is fine with just a hash function. Meanwhile XEX offers the advantage that it is more misuse-resistant (reuse of the counter/nonce breaks CTR but this is not an issue with XEX) and less malleabile. Considering that, why is XEX almost never used outside of disk encryption?


texts: CSIDH: Why do we need ideals in the form of $\langle \ell, \pi \pm 1 \rangle$ in order to apply Vélu's formulas when computing the action?

texts:
I am trying to understand the action of the CSIDH protocol.

Let $E_0:y^2=x^3+ax^2+bx$ be a Montgomery elliptic curve over $\mathbb{F}_p$ for some prime $p$. If we take $\mathcal{O}$ as $End_{\mathbb{F}_p}(E_0)$, then $Cl(\mathcal{O})$ acts on $\mathcal{E}\ell\ell(\mathcal{O})$ as follows:

Let $I\in Cl(\mathcal{O})$ an ideal. We define $H_I=\lbrace P\in E_0 \vert \alpha(P)=\mathcal{O} \text{ for all $\alpha \in I$} \rbrace$. The action is defined as below:

$I*E_0=E'$, where $E'$ is the unique curve such that there exists a unique separable isogeny
$$\phi:E_0\longrightarrow E'$$
With $\ker(\phi)=H_I$. In other words, the kernel of $\phi$ is the intersection of all $\ker(\alpha)$ where $\alpha \in I$.

In order to compute the $\phi$ and $E'$, papers on CSIDH make use of Velu's formulas. So far, I have found the following theorem which applies to Montgomery curves:

Let $K$ be a field with char($K$)$\neq$ $2$. Let $a\in K$ such that $a^2\neq 4$ and consider the Montgomery curve $E/K: y^2=x^3+ax^2+x$. Let $G\subset E(\bar{K})$ be a finit subgroup with $(0,0)\not \in G$ and let $\phi$ be a separable isogeny such that $\ker(\phi)=G$. Then, there is a curve $E'/K:y^2=x^3+Ax^2+x$ such that, up to composition with isomorphisms,
\begin{align*}
\phi: E &\longrightarrow E' \\
(x,y) &\mapsto (f(x),c_0yf'(x))
\end{align*}

where
$$f(x)=x{ \prod_{T\in G\setminus \lbrace \mathcal{O}_E \rbrace}^{} \frac{xx_T-1}{x-x_T}}$$
Furthermore, if we let
$$\pi=\prod_{T\in G\setminus \lbrace \mathcal{O}_E \rbrace}^{} x_T, \quad \quad \sigma=\sum_{T\in G\setminus \lbrace \mathcal{O}_E \rbrace}^{} \left( x_T-\frac{1}{x_T} \right)$$

Then, we have $A=\pi(a-3\sigma)$ and $c_o^2=\pi$.

So far so good, we have a way of computing isogenies between Montgomery elliptic curves. What I do not understand is the following. In several papers and slides, they explain that we have to take ideals $I\in \mathcal{O}$ with the form  $\langle \ell, \pi \pm 1 \rangle$, where $\ell$ is a prime. Analizing said ideals, we see the following:
$$H_I=\lbrace P \in E/\mathbb{F}_p \text{ } \vert \text{ } [\ell](P)=\mathcal{O},\pi (P)=P\rbrace$$

Since $\pi(P)=P$, it means that $P\in \mathbb{F}_p$. So it turns out that $H_I$ is just the $\ell$-torsion points defined over $\mathbb{F}_p$. The main claim is that we have to take $I$ in such a way because in doing so, we have a Vélu-friendly computation. This is what I fail to see. Why having rational points makes the Vélu computation easier?

In the theorem stated above, the hypothesis requires us that $G\subset E(\bar{K})$. But taking our ideal as $I=\langle[\ell]\rangle$ instead of $I=\langle [\ell], \pi \pm 1 \rangle$ also gives us a $H_I\subset E(\bar{K})$, which would be $G$ in the theorem notation, and so the theorem holds. Why is it then that having $H_I$ composed of rational points $P\in E(\mathbb{F}_p)$ makes the computation Vélu-friendly?


texts: FFX Encryption over alphabet of arbitrary radix

texts:
I understand how standard numeric FPE using a halved string in cycled Feistel networks is constructed and operates. I then read the paper regarding FFX encryption which should allow for any non-binary alphabet to also be used (http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/ffx/ffx-spec.pdf). However, I am having some trouble understanding how FFX works.

From what I can understand, the round function is the same, except FFX construction also allows for the two halves in the Feistel network to be split into different length strings. This also means that the round function is different, and changes to the described characterwise/blockwise function instead. However, I am not too sure how that method can work when the two halves of the string are no longer equal length. Perhaps I am misunderstanding something about how the XOR replacement works, so could someone help explain it?
*Also, I feel like my assumption about the round function may be incorrect. Does the round function need to be chosen out of a different set of PRFs than previously? (ie. not AES) <--- this is actually probably the case because of all the adjusted AES functions mentioned in the FFX paper

The addendum also explains how to construct the cipher while taking a parameter which specifies an arbitrary radix. I also do not understand this part.

Could someone give me a simple overview of how FFX encryption works?
Thanks!


texts: Why does anyone use elliptic curves for a CSPRNG?

texts:
I saw Martijn Grooten's talk on elliptic curves at BSides London this year, and it helped me understand how elliptic curve crypto works, especially in the case of Diffie-Hellman (ECDH). He also touched on the use of EC for random number generators (e.g. Dual_EC_DRBG) and why they can be flawed / backdoored.

This got me thinking: why do we even bother using EC for CSPRNGs? What drove us to even try? Surely block-cipher based CSPRNGs (e.g. AES-CTR) would be faster and more reliable, with no potential for "hidden number" backdoors? What is the key benefit that EC brings to the world of PRNGs, which outweighs their potential for weakness?


texts: Real-ideal world paradigm and adversarial models: how to model an adversary controlling the network only?

texts:
When proving the security of a cryptographic protocol using the real-ideal world paradigm (under sequential composability only) I have seen considering corruption of parties only in the adversarial model.
However, does it make sense to consider the case in which the adversary controls the network only explicitly, i.e, none of the parties is corrupted but the adversary has some power over the network (e.g., it can read messages)?
Or, can this case be expressed in terms of corruption of parties (so it does not have to be considered explictly)?


texts: What is the Limit on Maximum Number of Blocks to be Encrypted under One Key in CBC and CTR Mode? What happens if the limit is crossed and more number of blocks are encrypted?


texts: I was going through Path ORAM in oblivious RAM. I found it very interesting, as its promising but is there any scope left to enhance it?

texts: Is there any specific field in Path ORAM where I can further investigate or research?


texts:
I'm reading an unpublished paper in which the author makes the following conclusions several times:

Assumptions: finite probability space, $H$ is a random oracle, $X$ and $Y$ are two (not necessarily independent) random variables, $X \neq Y$ for every possible outcome.

Conclusion: $H(X)$ and $H(Y)$ are independent and uniformly distributed random variables.

"Proof" (not actually stated as such): obvious, $P(H(x) = a|D) = P(H(x) = a)$ for every event $D$.

Is this a valid conclusion? Are there any counterexamples which don't explicitly involve events $D$ similar to $H(x) \neq a$?


texts: Are there any real protocols secure in the random oracle model that have been broken in practice?

texts: Has any protocol ever been proven secure in the random oracle model and then broken in practice, despite the use of a good hash function in the actual implementation?


texts: Hash function such that fx(hash(s1),hash(s2)) = hash(concat(s1,s2))

texts:
First, I'm not a mathematician, so I may express this question awkwardly. Feel free to chuckle.

I'm wondering if there exists a hash function h such that for given strings s1 and s2, and string s3=concat(s1,s2), the hashes of s1 and s2 may be combined with a "hash combining function" g to give the hash of s3. That is g(h(s1),h(s2)) = h(s3).

For example, the string length function (as h) and addition function (as g) illustrate the property I'm after (even though string length would be a terrible hash function). For s1="abc" and s2="1234", s3="abc1234", h(s1) = 3, h(s2) = 4, and h(s3) = g(h(s1),h(s2)) = 7.

Merkle trees are similar in spirit to what I seek, except that I'd like the the intermediate hashes to be equal to the hash of the concatenation of underlying data (rather than a hash of child hashes).

For my intended uses, it is imperative that the hash function have an extremely low collision probability (akin to md5 or the sha series).

For what it's worth, the idea I'm considering is whether such a hash could be used to refer uniquely to a segment in graph of DNA sequence. Initially, the contiguous segment would be merely the hash of the segment, such as chromosome 1. As more is learned about large-scale genome variation, the contiguous segment might be decomposed into concatenated constituent segments, each of which is hashed. Users would refer to variation in sequence using the hash as an identifier, regardless of whether the sequence was contiguous or a virtual assembly of constituents. In this way, the hash value would effectively refer to both a path through these segments as well as the actual sequence of the concatenated fragments. For an example of such segments, see http://www.ncbi.nlm.nih.gov/assembly/GCF_000001405.28.


texts: The Secp256k1 curve is used in cryptocurrency. Can someone generate a private key with a different curve?

texts:
Many cryptocurrencies use Secp256k1.

Every cryptocurrency library comes with its own redundant implementation of Secp256k1, ECDSA, RIPEMD160, and SHA256. So, there can be some inconsistencies across implementations.

What if some library generates a private key using a different curve than Secp256k1? For example, one with less security, or even a backdoor. Choosing different points, etc.

Then they share only the public key with blockchain, of course. Is it possible that such a thing would work? Can some public key appear valid for Secp256k1, but in fact use another elliptic curve?

I just came across many open source cryptocurrency libraries where they generate private keys and everyone is using custom implementations of these. So I should at least compare source code and look for some specific set of constants.


texts: Has any alternative to RSA and Discrete Logarithm been standardized for deployment?

texts:
Suppose RSA and Discrete Logarithm over any group (including elliptic curves) gets broken what other schemes we have for DEPLOYMENT IMMEDIATELY do we have to rescue the internet from collapse?

So there is no other alternative and pretty much the internet is dead?

I see a lot of alternatives such as SVP based, code based alternatives floating around. Have any of these been standardized?


texts: Problem in Identifying relevant documents to evaluate Precision in Information Retrieval (IR) Systems

texts:
In searching engines, especially for ranked search approaches, How to evaluate the results returned by IR Systems . The precision is evaluated by the below equation:

(Number of relevant documents in retrieved documents)/(Number of retrieved documents).

However, how to decide which returned documents are relevant for the given query? For that, should we go through each returned document to find if it is relevant or not?  Or should we say if any returned document contains all the query keywords?


texts: In Elliptic Curve, what does the point at infinity look like?

texts:
We know that for each point $P$ in curve $E$ there exists a minimum scalar $k$ such that $k*P$ equals the point at infinity. And the book Cryptography Theory and Practice by Douglas R. Stinson only mentions that adding $P1=(x,y)$ and $P2=(x,-y)$ equals point at infinity $O$. But in terms of coordinates, how does the point at infinity look like?

The point at infinity is said to give $P+O=P$, but that is not evident from the book/tutorial. As an example, consider the curve $y^2=x^3+x +6$ mod 11 (this appears on slide 15 of this pdf and also on pages 185-186 of the aforementioned book). Taking $P=(2, 7)$ as the basis point, one generates all the points in $E$ up to point $(2, 4)$.

Now, $(2, 7)+(2, 4)$ is the so-called "point at infinity" $0$. But it is just unclear

how $0+(2, 7)=(2, 7)$, and
how $(2, 7)+(2, 4)$ should be visualized so that adding $(2, 7)$ again takes us back to $(2, 7)$.

Same slide (#15) also includes an example with curve $y^2=x^3+2x+3$ mod 5. Scalar multiplication on $P=(1, 1)$ "generates" all the points listed there except $(4, 0)$. How does one actually get to $(4, 0)$? I tried other "starting points" (e.g., $(3, 1)$) but to no avail.


texts: Why is triple-DES using three different keys vulnerable to a meet-in-the-middle-attack?

texts:
Among other sources, this wikipedia entry states that triple DES using three seperate keys (k1, k2, k3) is vulnerable to meet-in-the-middle-attacks, while triple DES using only two keys (k1, k2, k1) is not.

Why is this attack possible if all the keys are different, but not if the first and the third are the same?


texts:
In GSW homomorphic encryption scheme proposed here. The integers are over $Z_q$ where $q$ is a modulus parameter of the scheme. It is not clearly mentioned in paper if the ordinary representation of $Z_q$ (that is $\{0,1,..., q-1\}$) is used or balanced representation ($\{\lceil - q / 2 \rceil, ..., \lfloor(q - 1) / 2 \rfloor\}$). However, usually in lattice based cryptography a balanced representation is used since random numbers are sampled from truncated discrete Gaussian distribution. My question is, if negative numbers are used (which is the case in the balanced representation) how to perform the Bitdecompose procedure which performs the following:
Let $a \in Z_q$ and $l=\lfloor \log_2^q \rfloor+1$, $Bitdecompose(a)=(a_0, a_1, ..., a_{l-1})$, where $a_i$ is the $i$-th bit of the binary representation of $a$.


texts:
Let $R[G]$ or $RG$ be the group ring where $R=F_q$ and $G$ is any group. Let $Dim(V)=\vert G \vert$. It's clear that $V$ has $\vert R \vert^{\vert G \vert}$ distinct $\vert G \vert$-tuples. This structure is very similar to a polynomial quotient ring $F_q[x]/f(x)$ taken as a vector space, since the number of distinct tuples is $q^k$, and $k$ is the degree of $f(x)$.
From now I immediately start to think about applications on Cryptography. Been experimenting with it and multiplication is trivial to compute via programming. I'm able to enumerate the group of units but for now with trivial examples using naive methods (i.e: exponentiation). But for example, I have not tried to examine what happens when $G$ is a matrix group. Also, we can try to figure out how to use this structure as the platform group for existing schemes, so algorithms for computing necessary transformations (trapdoor, public/private generation, etc) must have a nice complexity.
Is there any scheme that works with group rings in any of its parts?


texts: Why does appending a message to a key before hashing not guarantee integrity?

texts:
I want to guarantee the integrity of a message $m$. My first thought is to append the message to an integrity key $k$ and hash it as $H(k\,||\,m)$. However, I have been told that this is not totally secure, because an attacker can add more data to the end of $m$ while still generating the correct MAC.

How is it possible for an attacker to modify $H(k\,||\,m)$ such that the message is changed but the MAC is the same?

I was advised to use HMAC instead. Why does HMAC solve this problem?


texts: Why is this attack complexity equal that exact number of bit operations?

texts:
in the this paper,section 3,autors attack hamsi-256. Im trying to make a parametrized version, so i need to understand how do they estimate the complexity of attack in bit operations,that reads as followed

Can anybody say why they dont count number of operations to generate a tree with $2^{224}$ leaves,and why is the summ looks like that? I know im asking a hard question, but i have noone to explaing such thing to me.


texts: ECIES: Purpose of optional shared information?

texts:
According to Wikipedia the ECIES algorithm has two optional shared information $S_1$ and $S_2$. They are used as follows:

Generate a random shared secret $Z$ according to ECIES, which will never be reused
Derive symmetric keys $k_1|k_2=KDF(Z_x|S_1)$
Encrypt the message $c=\text{ENCRYPT}_{k_1}(m)$
Tag the encrypted message $t=\text{MAC}_{k_2}(c|S_2)$

Question 1:
Assume:

$S_1$ and $S_2$ are randomly generated for each message and send with it in plain text.

Whats the purpose of $S_1$ and $S_2$ in this case? Whats the use of $S_2$ if $S_1$ is set properly?

Question 2: Assume:

$Z$ is not randomly generated for each message (e.g. using a static key pair)
$S_1$ and $S_2$ are empty

Is this mode secure? Or should it be avoided?

Question 3: Assume:

$Z$ is not randomly generated for each message (e.g. using a static key pair)
$S_1$ is a unique endless counter and send with the message in plain text

What is the purpose of $S_2$? Is it less secure to not use $S_2$?


texts: NTRU: Possible misunderstending of division and euclidean algorithm for polynomials

texts:
Please consider this answer before reading

I am trying to find GCD of two polynomials, but I have some troubles understanding division and euclidean algorithms:

1) In description of division algorithm it is stated that polynomial b must be of degree N-1, but when finding the inverse of polynomial we must pass $x^N - 1$ as b

2) If previous condition is ignored, division algorithm still won't work properly because of the next condition:

deg r >= N

if N is taken from parameter set, it doesn't make sence, because NTRU operates with polynomials of degree less than N.

So, consider next scenario:

$N = 11$

$a = -1 + x + x^2 + -x^4 + x^6 + x^9 + -x^{10}$

$b = x^N - 1 = x^{11} - 1$

Division algorithm would return quontient = 0 and remainder = a, since degree of a is less than N.

And the result will be the same regardless of the value of a.

What am I missing? I doubt that such basic algorithm could be documented wrong, so please help me understand what did I get wrong.


texts: What is the benefit of using elliptic curves over the standard finite field, when the cyclic subgroup we consider of the EC's  solution group is just isomorphic to some integer residue class of prime order? Is it because the group operation is more complex?


texts: What are the practical differences between 256-bit, 192-bit, and 128-bit AES encryption?

texts:
AES has several different variants:

AES-128
AES-192
AES-256

But why would someone prefer use one over another?


texts: Using the same RSA keypair to sign and encrypt

texts:
The RSA signature operation is basically the same as encrypting with the private key.  In particular, both operations use the same kind of keys.

Is it safe to use the same RSA keypair both for encryption / decryption and for signing / verification?


texts: Complexity of Discrete Logarithms in binary fields without special exponents or special structure

texts:
There has been recent work, due to Joux, Gologlu, Zumbragel and others which has developed efficient algorithms for discrete logarithms in small (and specifically binary) characteristics, where the exponents have some special form. See the discussion in the questions

how-robust-is-discrete-logarithm-in-GF(2^n)

and

do-recent-announcements-about-solving-the-dlp-in-gf26120-apply-to-schemes?noredirect=1&lq=1

My understanding is that discrete logarithms in $\operatorname{GF}(2^n)$ where $n$ is large and has no special for is still relatively robust to attacks.

Here is the question, say I pick $n$ large enough such that the multiplicative group $\operatorname{GF}(2^n)^{\ast}$ has no small subgroups. So either $2^n-1$ is prime, or $n$ is so large and well chosen that the largest subgroup is large enough.

Would the best algorithm in this case still be baby-step-giant-step for the discrete logarithm? Or something else of still exponential (in $n$) time and memory complexity?


texts: How do I unpack the x and y values from the BITSTRING in a DER ECDSA public key?

texts:
In ASN.1, the X and Y values for a 256-bit elliptic curve key are stored as a single 66-byte ASN.1 BITSTRING. Are the values just the first and second half of this bitstring?

The private key is an OCTET STRING at the beginning of the DER private key and I know what to do with it; the public key is a BITSTRING for some reason.


texts: What is the difference between RCCA and CCA2?

texts:
Well, I know it's easy to tell CCA1 from CCA2, but I failed to find the difference between RCCA and CCA2.

What is the difference?


texts: CSPRNG generation vs asymmetric encryption performance

texts: It might sound like a weird comparison, but which one is faster, If I were to generate a CSPRNG every time or to sign(private encrypt) a data?


texts: Does watching videos (either online videos such as off youtube or saved locally) generate enough (if any) entropy to create secure encryption keys? I understand that some activities such as memory usage, disk access, network utilization, using the mouse and keyboard, etc... generate entropy under Linux. What I don't know is if using the CPU and GPU also generates entropy? I also don't know if this is the same under Windows.


texts: What are the safe primes for $p$ and $q$ used in ElGamal?

texts:
I need to generate a 2048 bit key for ElGamal and I was looking for the $p$ and $q$ for PGP but I couldn't find them. the only thing I could find was this RFC but those are not safe primes.

Does anyone know where I can find those numbers?


texts: On Proving That a Primitive Does Not Exist

texts:
In the paper of Hsiao and Reyzin, Section $1.4$:

  Note that to show that no general reduction from $P$ to $Q$ exists requires proving that $Q$ does not exist

Since the statement is about trying to rule out the implication $Q \rightarrow P$, showing that $Q$ does not exist will indeed do the opposite: it makes the implication true for the trivial reason that $(\mathsf{false} \rightarrow \mathsf{proposition})$ is $\mathsf{true}$ for any $\mathsf{proposition}$.

Could someone explain?


texts: Is it possible to build short proofs of arbitrary computations over a big list?

texts:
With the use of Merkle Trees, you can prove the presence of an element of a very big list, with an amount of information logarithmic in the size of the whole tree. Merkle proofs, thus, probabilistically confirm the result of this specific fold:

isMember :: ∀ t . List t -> Bool
isMember e = foldr (\ h t -> h == e || t) False

My question is if the same result can be extended to arbitrary folds; or, in other words, is it possible to prove arbitrary computations about a big list using some clever trick similar to Merkle Trees?

Specifically, I want to store a huge dataset (>20 GB) on several computers, and then I want any of those nodes to make arbitrary claims about that dataset (like: the max element is 198500461354!), in such a way that other nodes can verify that claim is true without having to run max over the whole dataset themselves.


texts: Hard-core predicates: should the adversary be given $1^n$?

texts:
In most (all?) classical sources such as the book of Goldreich (2001), hard-core predicated are defined thus:

  A polynomial-time computable predicate $b : \{0,1\}^* \to \{0,1\}$ is a hard-core of a function $f$ if for every probabilistic polynomial-time (PPT) algorithm $A$, every positive polynomial $p$ and all sufficiently large $n$,
  $$\mathsf{Pr}\left[A(f(U_n)) = b(U_n)\right] < \frac{1}{2} + \frac{1}{p(n)}.$$

However, in the more recent book of Katz and Lindell (2015 for the second edition), $A$ is also given $1^n$. This seems to make a difference, for example for the following exercise:

  Show that any injective, polynomial-time computable function which has a hard-core predicate is one-way.

Under the Katz-Lindell definition of hard-core predicates, this is trivial: given a PPT adversary $A$ which can successfully invert such a function $f$, we construct a PPT adversary $B$ which can successfully compute any predicate $b$ for $f$ as follows. On input $(y, 1^n)$, $B$ runs $x' \gets A(y, 1^n)$ and outputs $b(x')$ if $f(x') = y$ and a random bit otherwise.

However, if $B$ is not given $1^n$, then it is not clear to me that it can determine in polynomial time the correct value of $n$ on which to run $A$. Goldreich also gives this exercise, but adds that "you may assume for simplicity that $f$ is length-preserving", which again makes it trivial.

In general, giving $1^n$ to the adversary seems to make the situation simpler, mainly because it makes the definition of hard-core predicates mirror that of one-way functions more closely, and if we assume (as is common) that $f$ is length-preserving, it is just redundant. I guess my question is: is there currently any consensus among researchers in this regard? Or are the two definitions actually equivalent (in which case I probably need to give in more thought...)?


texts: Algorithm Design for only Mutual Information Sharing

texts:
Bob and Alice each have a bit string they want to keep private. They each want to know what the bitwise AND of their two strings would be without telling the other or anyone else listening to their exchange their actual bit strings... how can they do this? Keep in mind that even once they both hold the AND of their two bit strings, they should still not be able to calculate the other person's string exactly (unless of course one of their strings was all 1s).

I know that I have seen something similar before in some sort of mutual key system/voting system but I couldn't remember where. It has to be something like make a private random key, xor it and use that somehow... but I couldn't work out the details. Any clever encryption design people out there?


texts: Prove the branch of number of Advanced Encryption Standard

texts:
In the Advanced Encryption Standard (AES) document: page 27 section 7.3.1, It defines branch number. It said

  " Let F be a linear transformation acting on byte vectors and let the
  byte weight of a vector be the number of nonzero bytes. The byte weight of a vector is denoted by $W(a)$.

  Definition: The branch number of a linear transformation $F$ is
    $$min_{a\neq0}(W(a) + W(F(a)))$$

  If the branch number is 5, a difference in 1 input (or output) byte propagates to all 4 output (or input) bytes, a 2-byte input (or output) difference to at least 3 output (or input) bytes. Moreover, a linear relation between input and output bits involves bits from at least 5 different bytes from input and output."

The AES chose polynomial $c(x)=03x^3+01x^2+01x+02$ to construct MixColumn operation , where the coefficients are hexadecimal representation of numbers in $GF_{256} $(e.g. $03_{hexadecimal}= 0000 0011_{binary} =\alpha+1_{polynomial\,representation}$) The MixColumn operation is done by multiplying $c(x)$ and mod $x^4+1$

However, the document doest not give a mathematical proof. My questions are

Prove the maximum branch number is $5$. Besides, AES MixColumn can achieve the maximum value as $5$.
given a branch number, how to construct the linear transforamtion
$F(\,)$ (in the case of AES, it is $5$) ?
Reversely, given $F$ (a matrix), how to estimate its branch number?
For example, how should I prove that if the linear transformation is
self-inverse
($\;(c(x))^2\equiv 1 \;mod\,x^4+1$ or $F^2=I$ ), then the
branch number is at most $4$?

I suppose these problems are related to matrix norm, but I do not know where to start to tackle these problems.


texts: XTS-AES uses two keys $(k_1, k_2)$, which are obtained from a concatenated key $k$. Does this key $k$ remain same for the whole disk or changes per sector?


texts: What is optimal error distribution in Ring-LWE?

texts:
I am new to Ring-LWE. I had assumed that error distribution in Ring-LWE (or, in any lattice-based cryptography) is always Gaussian.

However, while reading a few research papers (e.g. page 5, Section "Noise distribution and reconciliation" in https://www.usenix.org/system/files/conference/usenixsecurity16/sec16_paper_alkim.pdf), it looks like we can sample coefficients of error polynomial $e$, $e'$, $e''$ from Binomial or Uniform or any other distribution as well as long as the deviation is small.

Can someone please explain how we should choose error distribution?

EDIT: Watch this video on "The Mathematics of Lattices II" by Vinod Vaikuntanathan (MIT) - (between 32:50 and 34:40 where he discusses about error distribution) https://www.youtube.com/watch?v=SZkTJMorxnM


texts: Is there a complete list of Signature Algorithm names?

texts:
I need to analyze the output of rbsec's sslscan which reports a server's SSL/TLS configuration as reported by OpenSSL.

I'm interested in the Certificate's Signature Algorithm in particular, and I was hoping to find a complete list of possible values for this entry. During some quick tests, I saw that sslscan reports the long name for the algorithm. For example, RSA encryption with a SHA-512 hash is reported as "sha512WithRSAEncryption".

<certificate>
  <signature-algorithm>sha256WithRSAEncryption</signature-algorithm>
  ...
</certificate>

I've been trying for hours to pin down where these strings come from, and it seems that they aren't from the RFC specification for SSL (RFC 6101), but I could be wrong about that. I did find the names in OpenSSL's obj_dat.h file, however that header file contains a significant number of defined strings which are clearly not also signature algorithms.

  ...
  {"id-ppl-independent", "Independent", NID_Independent, 8, &so[4500]},
  {"RSA-SHA256", "sha256WithRSAEncryption", NID_sha256WithRSAEncryption, 9, &so[4508]},
  {"RSA-SHA384", "sha384WithRSAEncryption", NID_sha384WithRSAEncryption, 9, &so[4517]},
  {"RSA-SHA512", "sha512WithRSAEncryption", NID_sha512WithRSAEncryption, 9, &so[4526]},
  {"RSA-SHA224", "sha224WithRSAEncryption", NID_sha224WithRSAEncryption, 9, &so[4535]},
  {"SHA256", "sha256", NID_sha256, 9, &so[4544]},
  ...

Is there a list of the (OpenSSL specific?) long names for the Signature Algorithms that OpenSSL reports? Preferably one that is easily digestible for a program or human?


texts: 1-2 Oblivious Transfer - Can the recepient obtain both secrets by manipulating v?

texts:
Refer to the chart on 1-2 oblivious transfer : https://en.wikipedia.org/wiki/Oblivious_transfer
I'm Bob, I know N,e,x0,x1. Can I send Alice a v value that, by knowing the m'0,m'1 received, I can crack both m0 and m1?
Thank you


texts: Algorithm for factoring a 30 decimal digit number

texts:
My professor has given me an RSA factoring problem as an assignment. The given modulus is 30 decimal digits long. I have been searching a lot about factoring algorithms. But it has been quite a headache to choose one for my given requirements. Which algorithms give the best performance for 30 decimal digit numbers?

Note: So far I have read about Brute force approach and Quadratic Sieve. The latter is complex and the former time consuming.


texts: What do the last chunks of the output string of Scrypt contain?

texts:
When you use scrypt to hash a string, it will generate something like:

SCRYPT:4096:8:1:8zCQhTI8y2pdrFeIj2WYBJIbaLiePLOuXdbevG7XDV4qgUuiGPCXPFjh1aEmXQ/5u+SlCvz0KkcoOJtUWBkytfkCs2OZep60W+Nagv0gixqkcMn/PxoIqnOGIzyDWntEdsQKjYBHDYK5Va5VDHqoQxJeIm+yq3lJ4/y5dnL55RA=:zABi6opzkXwG627OUrk4KNUCiajY1xdM+PVmSC+VJS8=

The first part: SCRYPT:4096:8:1: is the "header" (identification and parameters used).

The second part:

zCQhTI8y2pdrFeIj2WYBJIbaLiePLOuXdbevG7XDV4qgUuiGPCXPFjh1aEmXQ/5u+SlCvz0KkcoOJtUWBkytfkCs2OZep60W+Nagv0gixqkcMn/PxoIqnOGIzyDWntEdsQKjYBHDYK5Va5VDHqoQxJeIm+yq3lJ4/y5dnL55RA=`

I believe is the actual hash (b64 encoded).

What is the last part? zABi6opzkXwG627OUrk4KNUCiajY1xdM+PVmSC+VJS8=, the salt?

UPDATE

I found this question: https://security.stackexchange.com/questions/88678/why-does-node-js-scrypt-function-use-hmac-this-way/91050#91050

bytes 0-5: The word "scrypt"
bytes 6-15: Scrypt parameters N, r, and p
bytes 16-47: 32 bits of random salt
bytes 48-63: A 16 bit checksum
bytes 64-95: A 32 bit HMAC of bytes 0 to 63 using a key produced by the scrypt key derivation function.

To my understanding, it describes the first and second part of the resulting string described previously. Unless I'm mistaken, the last part is not discussed there.

Bottom line

As commented by Maarten Bodewes, I have found that not all libraries will output the same string as I posted above. That one is specific for the Perl library I'm using (I was unaware of that). For example, take a look to these implementations, and you will see the hash doesn't look like that:

https://github.com/pbhogan/scrypt#how-to-use-scrypt
https://github.com/barrysteyn/node-scrypt#if-random-salts-are-used-why-do-all-resulting-kdfs-start-with-c2nyexb0


texts: Are those two distributions indistinguishable?

texts:
The Decision composite residuosity problem problem states that is impossible to distinguish between those two ensembles:
$\{x^N \mod {N^2} | x \in \mathbb{Z^*_{N{^2}}}\}$ and $\{r  \in \mathbb{Z^*_{N{^2}}}\}$

Can we assume the same for these:
$\{x-1+x^N \mod {N^2} | x \in \mathbb{Z^*_{N{^2}}}\}$ and $\{r  \in \mathbb{Z^*_{N{^2}}}\}$


texts: Implications of TLS-SRP client with improper N validation?

texts:
During development of a client side application of TLS-SRP, i noticed a bug that allows an attacker spoofing as the server to send custom, but non-arbitrary $N$ values, with the client accepting them. Having fixed it immediately, i'm still curious to understand what the implication might have been.

The client has a known-good $N$ value stored in memory, taken from the SRP RFC, comprised of bytes $N_0...N_n$, against which the N received from the server is compared. The issue is that exploiting the above bug, it is possible to trick the client to accept an arbitrary-length prefix of the good $N$ value (i.e. $N_{smaller}=N_0...N_k | k < n$). Alternatively, the client can be tricked to accept a larger $N_{larger} > N$ ($N_{larger}=N_0...N_j|j>n$), where the trailing bytes ($N_{n+1}...N_j$) are known to the attacker but cannot be specially crafted.

What attack vectors does this kind of vulnerability open up, and how should N be crafted to achieve it?
For example, can an attacker successfully spoof as the server without knowing the password / verifier?
Can an attacker calculate $x$ (password + identifier hash) for later authentication as the client? Can an attacker calculate the private key $a$ out of $A$ ($A = g^a $ $mod$ $N$)?
TLS-SRP RFC: https://tools.ietf.org/html/rfc5054


texts: what are multi-primes and how are they different from semiprimes?

texts:
I came to know of semiprimes recently. The simplest explanation of semiprimes is you take any two prime numbers and you multiply them, say 3*11 = 33 in which case 33 would be a semiprime. The numbers may grow bigger but the idea is same.

Hypothetically (or maybe in reality as well), you could use a good large semiprime as your public key and one of the primes as the private key so encoding and decoding is simpler for the one who has access to the private key.

Now what is/are multi-primes? Are they multiple prime numbers which are multiplying with each other or some other thing ? As in the above scenario, if somebody encodes some data with result of multiplication of 3 or more primes. In this case, how would the above example work while decoding the data?

Looking forward to know and understand. I did use various search engines but didn't get any explanations for this.

Looking forward to know.


texts: Can cryptographically useful pairings only be used with elliptic curves?

texts:
As far as I understand one big advantage of ECC is that we can use pairings on the group of torsion points of the curve.
I was wondering if it is possible to construct pairings from general finite fields $\mathbb F_q$?
If not on finite fields $\mathbb F_q$ are there other structures in cryptography where pairings are used?


texts: Lehmer random number generator cipher - looking for differentials

texts:
I'm looking for differentials in my kind of toy encryption scheme. I can't find any.
Let's consider linear congruential generator:
$X_{k+1} = a \cdot X_{k} \mod 2^{128}$
Such that $a$ is some number which for every 128-bit input $X_{k}$ from $0$ to $2^{128}-1$ will give us different output $X_{k+1}$ from $0$ to $2^{128}-1$. So we got bijection here (we can find many such odd $a$). Now let's say we will choose such 128-bit $a_{1},a_{2}, ..., a_{10}$ as a keys, randomly. We make $10$ rounds of encryption like that:

$a_{1} \cdot INPUT \mod 2^{128}$
Reverse $128$-bit block.
$a_{2} \cdot (2^{128}-INPUT) \mod 2^{128}$
$a_{3} \cdot INPUT \mod 2^{128}$
Reverse $128$-bit block.
$a_{4} \cdot (2^{128}-INPUT) \mod 2^{128}$

and so on...
Do you see any differentials here? Let's skip the encryption problems with zero-block - it can be solve easily, for example if we will use xoring before every round. Of course it is just keyed Lehmer random number generator with a modulus which is a power of two - and such generators have problems with low bits, but I can't use it to find differentials in that case.


texts: Assuming a 1024qb quantum computer, how long to brute force 1024bit RSA, 256bit AES and 512bit SHA512

texts:
Assuming in the future there was a functioning 1024 qubit quantum supercomputer and it could run Shor's algorithm or Grover's algorithm to crack encryption very quickly. I'm interested in how the number of qubits translates to performance improvement over a regular 2 bit computer.

For example, if I used Shor's algorithm on a 4 qubit quantum supercomputer, would this take half the time to factor 1024 bit RSA as it would a regular 2 bit supercomputer? Then if we extrapolate upwards to 8 qubit supercomputer through to 512 qubit, 1024 qubit and even 2048 qubit etc. What sort of factorization speed increase would you get from adding more qubits? I originally thought quantum computers could have only 4 qubits. But it seems these days you can keep adding qubits up to the amount you want within technical reason. Does this mean if I had a 1024 qubit supercomputer I could factor RSA 1024 bit in a split second? At what speed could it check possible factorizations?

So I'm interested how long it would "theoretically" take to:

Brute force find the key for a 1024 bit encrypted RSA message using Shor's algorithm.
Brute force find the key for a 256 bit AES encrypted message using Grover's algorithm.
Find a pre-image for a SHA2-512 bit hash.
Construct a rainbow table for a SHA2-512 bit hash.
If people are using 2048 bit RSA now as standard, will it take double the above time?

Some explanation for how to calculate that and a breakdown into the time it would take in seconds, minutes, hours, days or years would be much appreciated.


texts: How does Dragonfly key exchange work, in non-white-paper terms?

texts:
I'm trying to understand WPA3, whose Simultaneous Authentication of Equals is supposedly similar to Dragonfly Key Exchange.

Dragonfly is resistant to dictionary attacks, meaning that rather than an attacker being able to identify the use of a password in their dictionary with passive computation, they are forced to interact with one of the parties to make guesses.

I'm having trouble understanding the description of Dragonfly in the link, which is the only one I can find. How do Dragonfly's properties arise from the arithmetic? Is it some property of the "hunting-and-pecking" that only the non-attacker parties can perform the computation?


texts: How to prevent reflection attack in Needham-Schroeder in ECB mode?

texts:
We know that Needham-Schroeder is vulnerable to a reflection attack as shown here.
How can I make it secure using ECB and without using timestamps? I need to modify the protocol. Otwan-Rees is a possible solution. Is there any other way which doesn't deviate much from the original protocol.


texts: Optimized modular multiplicative inverse for Bitcoin (secp256k1)

texts:
I have written an application to brute-force attack Bitcoin addresses for OpenCL. It implements a simple exhaustive search starting from public key G (private key 1) and point increment (addition of G) to get next key.

It works, but its performance is one order of magnitude slower than its CPU implementation using GMP (same point increment algorithm but with GMP routines instead of custom ones). On GMP implementation, hashing is the bottleneck. On OpenCL implementation, point increment is the bottleneck.

My point increment implementation uses modular multiplicative inverse via binary extended GCD (algorithm 14.61 of Handbook of Applied Cryptography). It is one order of magnitude slower than GMP implementation using mpz_invert().

What I need is an optimized point increment (point addition with G) optimized for curve secp256k1. This is an educational project, so my knowledge about the subject is limited. I don't know if there is a way to accomplish it without using modular multiplicative inverse or if there is a way to speed up this calculation for my particular application.

I saw and implementation (by Segher Boessenkool) using modular exponentiation with precomputed values, but there was no information on how to get those values for other curves. I failed to replicate GMP implementation. Its source code is huge and a mess of mixed optimized C and assembly code impossible to understand for me.

Requirements:

A fast point addition by G implementation.
Safety is irrelevant due to its use.
If possible, optimized for curve secp256k1.
If possible, precompute as much as possible.

Question:

How can I improve speed of elliptic curve point addition in my specific case?

Notes on comments:

The search is sequential inside each OpenCL kernel, but parallel considering the whole program. My worksize is optimized experimentally, getting close to theoretical GPU FLOPS performing SHA-256 only, so the bottleneck is not in OpenCL usage, but algorithmic implementation of elliptic curve cryptography.
The performance one order of magnitude smaller I am talking about is measured on CPU, not GPU. I get about 30 kKeys/s with my own modular multiplicative inverse and 200 kKeys/s (a laptop) with GMP. On GPU I get about 2 MKeys/s. Computing unoptimized SHA-256+RIPEMD-160 hash only, without point addition, I get about 1 GHashes/s (AMD Radeon RX 580).
Main program computes an array of public keys using scalar multiplication. It can compute them pseudo-randomly or equally spaced. This array is feed to the OpenCL kernel, and each instance computes RIPEMD160(SHA256(P)) == TARGET, RIPEMD160(SHA256(P+G)) == TARGET, RIPEMD160(SHA256(P+2G)) == TARGET, ... For now, there is only a single target address.
OpenCL is not the issue here. Profiling on CPU reveals that 90% of the time is expend computing modular multiplicative inverse. Same algorithm with GMP mpz_invert() uses only 25% of the time to do same step, using the remaining time on hash computation.


texts: Is concatenated data hashed with scrypt vulunarable to a length extension attack?

texts:
scrypt takes a salt, and a password plus some cost paramters to generate a key. So say we define it as this:

key = scrypt(password, salt, cost)

I am interested in using it for generating passwords deterministically. E.g. to create a password for amazon or apple I would so something like:

amazonpassword = base64(scrypt("username" + "masterpassword", "amazon", cost))
applepassword  = base64(scrypt("username" + "masterpassword", "apple", cost))

So I wonder if this is suspectable to a length extenson attack. E.g. if an attack found out what:

scrypt("masterpassword", "amazon", cost)

is, could they then use that as a basis for guessing what:

scrypt("username" + "masterpassword", "amazon", cost)

is? If so what is the best approach for avoiding this problem? Should I use a HMAC to generate the masterpassword string?


texts: Doubts about Authenticated Data Structures logic

texts:
I am studying the theory of authenticated data structures, like Merkle Trees and I have a doubt: Why use them?

For example, to be sure that a cloud provider didn't modify my files, why do I have to ask for a particular data block and have the cloud reply with a hash path from the leaf to the root to authenticate all the tree (and then all the database)?

Isn't it simpler to ask a for particular piece of the DB (suppose the DB is divided in blocks) and receive from the cloud provider that block with a digital signature?
In this way, I can ask continually for a lot of blocks without using a Merkle tree at all.

I am reading materials about the RSA accumulator, bilinear maps, Bloom filters, etc., and every time I read about different protocols built over particular data structures.

Since using these techniques has a computational cost (e.g., RSA accumulators can be expensive) my question is as asked before:
Instead of having a single digest that authenticates the entire set or DB, why not require different pieces of data with the digital signature?

I hope you can answer my strange question!

Thank you!


texts: Is this cumbersome strategy to produce a ridiculously strong password valid?

texts:
I'm writing something where somebody wants to have a ridiculously strong password for a file and yet be sure that he will always be able to reconstruct it. The way I have thought of this might be a little cumbersome, but as long as it works and makes sense, I'm happy with it. First I'll explain how my character derives his password, and then the issues I'm having.
Password derivation
My character will start from a sentence describing something only he knows. Then he will transform it so that it wouldn't look like a sentence to anybody (remove spaces, replace letters with numbers or symbols at random places, replace syllables with similar-sounding ones, random capitalisation, etc.) leading to what we'll call the base password.
Not happy with this level of security, he wants to generate a much higher-entropy password by running the base password through an encryption algorithm a certain number of times. There are very subtle hints that will remind him what algorithm and key he needs to use, and how many times the base password needs to be run through it. The final result is the file password. (He doesn't need to open the file often so it's alright to have to go through the hassle when he does need to open it.)
I did a test using Twofish and running a base password through it a few times. I got this stuff:

rvXRimTU7jhLxCZCe+9hCafIj/5nwZ4eK4pDJOxi5+8yulVzG6h61bZBIK5E2fCcHiG65HaoybnhH9/2l2VnGjWiqH44Snr9iSGInq0vwApJUAalYMJRDwXNQh2yOr6yRtqA+CtWZrbCu86IGjLy6NB5C75ko3khsz342JW94Uj7GrZDZWKee3M2KB3O76QbXtVB8EiBhuvoHeeEOvskeJdw5qAfPw42j4aQdAdcfc6Qo1cHIh20piWy8xrnvywViXM1tpEFBezbPXHBFjCUp1vFJAFf/vDl9SMA7pD7B190jZxQHpltAJeQXJxwAoM64fvxGTNx/Cieo4s+WHnCTA==

Questions and issues

To me, the resulting file password looks high-entropy enough. Unless an attacker can guess the original sentence, how it was turned into the base password, and gets the hint revealing the algorithm used to scramble it, I doubt anyone could brute-force that file. Yes, they could hit the character with a wrench until he reveals how to get the file password and stuff like that, but we don't care about that. We only care whether the file password is high-entropy or not. Do you guys agree that it's high-entropy?

I used an online tool to do my test, and that's when I was reminded that encryption algorithms often use "salts" to make the result different each time even though you encrypt the same data with the same key. Clearly, this is a problem, because if salt is used then our character will never get the same password again. Is salt the only factor that adds randomness in Twofish, or is there other stuff I need to take into account? (I can simply assume he is using an implementation that excludes all randomness and always generates the same file password from the same base password, provided the correct key is used and the algorithm is iterated the correct number of times.)

I was rather disappointed to see that different online tools for text encryption are utterly incapable of correctly decrypting each other's output even with the same settings and the correct key. The result is invariably gibberish. This is going to be an extremely dumb question, but I guess this depends on the implementation, and that if we had two professional tools implementing Twofish, they should be able to decrypt each other's output given the correct key and the same settings? (If this wasn't the case, other people in the story would never be able to access the encrypted file.)

Is the method I outlined sensible, from a security standpoint?


texts: Is there a general method to crack this type of fractionating cipher?

texts:
I've seen a few puzzles based on a type of cipher in which letters in the plaintext are substituted with groups of characters in the ciphertext.  The ciphertext only uses a handful of unique characters.  For example:

a -> 154
b -> 53
c -> 12
d -> 41
e -> 153
...

In this example, bead is encoded as 5315315441.

Since not all letters are encrypted to have the same length, I can't simply break the message up into pairs of numbers and run frequency analysis.  Once the key is known, however, then the character boundaries are unambiguous.

Difficulties in cryptanalysis also arise when one letter's encryption completely contains another letter's encryption, such as how e 153 contains b 53.  For example, the following is unambiguous given knowledge of the key, yet might not be easy to for an attacker notice:

  4153 -> db
154153 -> ae

Let's say that I have a ciphertext, and I am reasonably sure that it is encoded in this way.  How would I go about cracking it?

The only thing I know to do is to look for repeating patterns, as repeating words in the plaintext also repeat in the ciphertext.  I haven't successfully solved one of these kinds of puzzles, however.


texts: Does it make sense to block RSA keys under 1024 bits?

texts:
A paper I found (http://eprint.iacr.org/2012/064.pdf, which was submitted to a cryptography conference about two years ago), is based on the analysis of some 7.1 million 1024-bit RSA keys published online. By subjecting the modulus of each public key to an algorithm first postulated more than 2,000 years ago by the Greek mathematician Euclid, the researchers looked for underlying factors that were used more than once. Almost 27,000 of the keys they examined were cryptographically worthless because one of the factors used to generate them was used by at least one other key.

As these findings were related to 1024-bit RSA keys (and even those show some points of weakness), does it make sense to generally block all RSA keys under 1024 bits to enforce/strengthen used crypto?


texts: Block Cipher CTR mode when offset is not known by receiver

texts:
When an encrypted message is received, it can be easily decrypted if the offset (=counter) of the received message is known (and also the required private key of course). This allows for random access on decryption. What if the receiver somehow forgot to keep track of the counter. Can the receiver still recreate the original plaintext? Or is it required that every received encrypted text is asigned a resp. counter value upon arrival? Or is this counter passed in some way such that the receiver does not have to keep track of it, e.g. as an additional parameter.

A scenario I was thinking of is that when the receiver missed the first N blocks. He/she would then not know the current counter resulting in not being able to decrypt.


texts: Using states of a double pendulum as a one-way function

texts:
Hello,

as a non-professional (at all) but a fan of cryptography, I have one idea and I would love to hear your input on it.

As I understand cryptographic functions they should have following attributes:

from private to public part - fast and easy
from public to private - hard

Ok, thats the basis premises I will try to follow.

This works for RSA and elliptic curves and so on... If I understand it right.

Now to the idea:

I have checked a documentary on double pendulum and chaos theory and I find it a very nice idea so I thought like, why not using similar one?

For some details on double pendulum examples see:
http://www.tapdancinggoats.com/double-pendulum

Ok as output there would be the states of pendulums after simulation.

And as for input there would be initial: position, amount, mass of the pendulums and length of the simulation.

It should not be a problem of simulation the process with initial data, but there should be a problem on finding the correct initial state.

What do you think? Is this idea worth looking into? :)

Thank you

Oliver


texts: Does using Noise asynchronously weaken its security properties?

texts:
Can Noise be used asynchronously without weakening its security properties?
Specifically, there are two users, A and B, who communicate asynchronously by leaving messages for each other on an untrusted server, but they may never be online at the same time. They know each other's public static keys in advance, so the KK pattern seems appropriate:
KK:
  -> s
  <- s
  ...
  -> e, es, ss
  <- e, ee, se

It seems to me that this pattern could be used asynchronously without weakening it.
A and B both initially upload a bunch of ephemeral public keys to the server, and top up the supply when they connect at later times.
Now A wants to send a message to B:

Download one of B's ephemeral keys from the server, and run the first handshake step.
Run the second handshake step, generating an encrypted public ephemeral key (so handshake is done).
Run Noise again with the plain-text as a payload, generating an encrypted transport message.
Upload a concatenation of B's plain-text ephemeral key, A's encrypted ephemeral key, and the encrypted message.

When B comes online and downloads the message, they:

Discard the message if the plain-text ephemeral key is not on their list of unused keys.
Run the two steps of the handshake.
Decrypt the encrypted message.

(So in this scenario, B is the initiator and A is the responder.)
I hope this is not off-topic. I thought it was OK because I'm asking more about how to use an existing protocol rather than asking for cryptanalysis of my own design.
Edit 27 August
I found a gotcha in the above scheme today. In section 7.5 of the spec it says:

...patterns starting with K or I have the caveat that the responder is only guaranteed "weak" forward secrecy for the transport messages it sends until it receives a transport message from the initiator. After receiving a transport message from the initiator, the responder becomes assured of "strong" forward secrecy.

So my scheme will only have weak forward secrecy, which is a shame, because the whole point of using Noise was to get forward secrecy. I think X3DH (as used by Signal), gets around this by signing the prekeys (the initial shared ephemeral keys).


texts: AES S-Box implementation: from a byte-by-byte to 2-bytes-by-2bytes?

texts: The S-Box in AES encryption is a byte substitution step. Is it possible to perform the substitution 2 bytes at a time, rather than 1 byte? What are the challenges/trade-offs involved?


texts: How can I process data within a cloud securely?

texts:
I'm new to programming and I'm getting ready to design a proof of concept for an app that I'm thinking of building. Problem is I'm a complete noob to cryptography and need a little nudge to point me in the right direction.

I would like to design a method by which data sent to my application on a cloud server is processed securely.

Here is a scenario:
1. Company A publishes XML file on their server and makes it available via SFTP.
2. A process on Cloud Server uses SFTP to fetch the data from Company A's server.
3. Cloud Server parses the XML based on a defined format, but it must do so securely so that even the server admin cannot see the processed data.
4. Cloud Server rebundles the parsed XML data into emails that are transmitted via SSL to Company B.

Step 3 is what I need some help with. SFTP and SSL are good enough for the pull and transmit side of things. I'm just wondering how to secure the XML such that my app can do what it needs to do given the right keys - but I don't want to know the keys. The keys would need to be known only by Company A (publisher) and the recipient (Company B). And if there was a problem, Company B could login to Cloud Server via a web page and view their data unencrypted given they have their key.

I've seen businesses in the email archiving and file storing space that can blindly encrypt data so that they cannot ever view your data. (Proofpoint, SecureSend are examples) If you lose your key, they cannot decrypt your data. I'm thinking my process would use something similar.

Would anyone know the method or process that can do this? Thank you.


texts: Why are digital signatures used when performing DH?

texts:
Suppose the server has a public key which everyone knows is associated with it, maybe it's hardcoded into the browser or signed by some CA.

At no point do you need the server to sign anything with it, the client generates an ephemeral key pair, performs DH with the server's public key and sends his ephemeral public key followed by a symmetrically encrypted message.

Only the server and client now have a shared secret. The client can reject any reply that does not contain something encrypted with the symmetric key.

If forward secrecy is required the server's ephemeral key can be contained inside the encrypted message when it replies. So why do all the schemes use digital signatures in key exchange?

tldr: If you are able to verify a signature you have a public key to work with, if you have that then why not just do DH with it?


texts: Changing encryption key without revealing the original key

texts:
Say that Alice encrypts a $\text{plaintext}$ with $\text{key}_{m}$ and gives the $\text{ciphertext}_m$ to Bob. Alice wants to send several gigabytes of $\text{plaintext}$ to Eve but she is on a mobile 3G connection. So instead, Alice and Eve exchange a new secret $\text{key}_{eve}$. She then creates a $\text{key}_{mutate} = \operatorname{Keymutate}(\text{key}_m, \text{key}_{eve})$ and sends it Bob where he applies a mutation function to produce $\text{ciphertext}_{eve} = \operatorname{Mutate}(\text{ciphertext}_m, \text{key}_{mutate})$. Bob sends the $\text{ciphertext}_{eve}$ to Eve and she produces the $\text{plaintext} = \operatorname{Decrypt}(\text{ciphertext}_{eve}, \text{key}_{eve})$.

This seems like a homomorphic encryption cryptosystem, does something like this possible or even implemented?


texts: How would I convert committed coordinates $x$ and $y$ to a commitment of the EC point without revealing the point (in Zero Knowledge) or vice versa?

texts:
I am working in the secp256k1 elliptical curve, though I suspect this would apply to any elliptical curve.  I have a Pedersen Commitment of the $x$ and $y$ coordinates in some discrete log scheme with generators $g$ and $h$. The point described by $x$ and $y$ is equal to $G^n$, where $G$ a public generator and $n$ is a secret (using exponentiation to represent point scalar multiplication on elliptic curves). Is there a method to get from the $g^x h^{r_1}$ and $g^y  h^{r_2}$ to $G^n H^{r_3}$, where $H$ is a second generator in the curve and all $r$ values are secret random numbers, using Zero Knowledge Proofs where needed?  A method in the other direction, going from the commitment of $n$ to a commitment of the two coordinates $x$ and $y$ would also be applicable.  I haven't been able to find such a proof in my research and I have not been able to think about how to create one.

My goal is to design a Zero Knowledge Proof of Knowledge of the private key associated with a public key which has been hashed (using the Bitcoin address hash) in such a way that the only public information is the environments (generators, settings, etc) and the result of the hash function, as well as all associated functions like the Bitcoin Hash. This proof can be used to prove ownership of a non-spending Bitcoin account without revealing the public key. If someone has done this, then I guess the question is moot and I will reference an applicable paper instead of designing it myself, thus a link to any such paper would also be an acceptable answer to this question. Unfortunately, I have not seen such a paper myself in my research.

EDIT:

I should also note that before the commitments of the coordinates were in the form $g^x h^{r_1}$ and $g^y h^{r_2}$, they were two lists of bitwise commitments that were homomorphically combined to become $g^x h^{r_1}$ and $g^y h^{r_2}$.  I did not lose those commitments, so they are available.  It was probably a mistake to suggest combining them, as it could introduce problems in performing operations on them due to differing orders between groups.


texts:
An old project that I did not code is using the KDF3 algorithm, but I struggle to find an explanation about the way this key derivation algorithm works.
I know that this algorithm is part of the ISO-18033-2:2006, but it is pretty expensive.

Can someone explain it to me ?


texts:
The last days I was looking for a way to encrypt using ECC, without having to make the program myself. I was sure that someone should have done it for everyone by now.

The best approach I had was with bouncy castle. The bad thing about it, is that I never found a "encrypt" or "decrypt" method. The best thing I could found was a sign method and a verify method. The thing is that I read about hybrid encryption, so I was trying to encrypt something with this method, so the signature isn't enough.

Also I've seen code that uses the Cipher class. But after implementing what it said and the execution failed, I saw at the Cipher class documentation that ECC is not implemented there.

Thanks for the help


texts: Can i XOR an array of bytes with an equal length key securely

texts:
If i have say 64 bytes, can i XOR those bytes with another 64 random bytes, and have two new arrays, where both are needed to reconstruct the first?

Intuetively i need some symmetric encryption like AES, but i cant figure out how the XOR above can be attacked. Does the content matter?


texts: In ECDSA, without knowing private key and any signature one can sign random garbage (from the Cryptography list)


texts: Coefficients of Elliptic Curve over Finite Fields

texts:
When talking about elliptic curve over finite fields in ECC, we often assume that the elliptic curve can be written in the Weierstrass form

$$y^2=x^3+Ax+B, \quad A,B\in \mathbb{F}_q$$.

where $\mathbb{F}_q$ is a field of characteristic not $2$ and $3$. (For example, Schoof's algorithm to compute $\#E(\mathbb{F}_q)$ assumes this. )

In practice, would $A$ and $B$ ever be non-integer coefficients(suppose we are working over $q=p^n$)? That is to say $A=\underbrace{1+...+1}_{\text{sum of }1}$ or might we pick $A,B$ to be other elements from $\mathbb{F}_q$?
How would these algorithms that assume the Weierstrass model, generalize to say elliptic curves over fields of characteristic $2$ or $3$? For example, Koblitz curves are a class of elliptic curves of the form $y^2+xy=x^3+ax+1$ in $\mathbb{F}_{2^m}$?


texts: Why commutativity gives an invariant subspace?

texts:
In A Generic Approach to Invariant Subspace Attacks the authors defined an invariant subspace as:
$$F(u + A) = v + A$$

Where $F:\mathbb{F}_2^n \to \mathbb{F}_2^n$,$u, v \in \mathbb{F}_2^n$,  and $A$ is a linear subspace.

Then they claimed that if $M\circ F = F\circ M$ for a linear subspace $M$ then $A:=ker\left(M+Id\right)$ is a linear subspace(Lemma 2).

I couldn't figure out why this is true for any bijective $F$ function. Any idea how to prove it?


texts: Key strength comparison: symmetric key vs RSA/DH key

texts:
I came across different reputable sources quoting different equivalent symmetric key strengths for RSA/DH keys. This NIST paper (page 67) states the following offer corresponding security strenghts (symmetric / public):

80 - 1024
112 - 2048
128 - 3072

This is in line with the following paper by RSA Labs:

80 - 1024
112 - 2048

However, in "Serious Cryptography" by Jean-Philippe Aumasson author gives slightly different estimates:

70 - 1024
90 - 2048
128 - 4096

What could be the reason for these discrepancies?


texts: How to store the ciphertext generated by the paillier encryption in a pixel?

texts:
Goal:
I want to implement a paillier algorithm to encrypt images and hide some data reversibly.
This is the paper that proposed this algorithm:
https://www.sciencedirect.com/science/article/abs/pii/S1047320316301808
(this link can be obtained for free on sci-hub: sci-hub.tw)
Question:
The paper mentioned that paillier encryption is performed on each pixel, and the data is hidden in the ciphertext, and then the ciphertext is stored in the picture. We all know that the range of the gray value of a pixel is 0-255, but the paillier ciphertext may be 1024bits. If the ciphertext is modulo 256, then a lot of data will be lost and the original image cannot be restored.
My question is how to store the large integer ciphertext generated after encrypting a pixel in the pixel.I think it is impossible to store 1024bits of ciphertext on an 8bits pixel. :)
What I've tried
In order to solve this problem, I searched some related papers and some implementations of the algorithm, but none of them solved my problem.

In some implementations, a smaller N, 7-8bits, is selected during paillier encryption.Obviously, this can guarantee the normal encryption and decryption of the picture, but there are two problems: first, you cannot hide data in the ciphertext like in the paper; second, due to the characteristics of paillier encryption, N is easily factored, which means this It is not safe.
There are also some implementations. After the two-dimensional array of image gray values is encrypted pixel by pixel, it is then decrypted, and the decrypted array is converted into a picture and saved, but the two-dimensional array of ciphertext in the process is not converted into a picture (because pixel value cannot be a large integer), then in practical applications, how should the two-dimensional array with each element be a large integer be stored? If it is stored in text form, how to generate the several encrypted pictures given in the paper.

I am a newbie who loves cryptography and hope to get answers to the question that have plagued me for several days.


texts:
I've just been reading the Why should I make my cipher public? question and answers on this site.

I understand Kerckhoffs's principle, but I'm unsure exactly how this applies to Enigma - i.e. where the delineation is between algorithm and key.

(I feel I should know, but I haven't quite gotten there.) Here's what I think I know:

The wiring of the rotors & plugboard = part of the algorithm
The starting positions of the rotors = part of the key

Assuming #2 is correct, how would you define the order in which the rotors are set, or which ones are selected - is that merely altering the algorithm?


texts: What's the difference between this mentioned list and a certification revocation list?

texts: I've come across this paper in which the authors mentioned that they don't use a revocation certification list (CRL) since it gives rise to significant costs due to storage and inefficient communication. But then in section 4-F (VEHICLE REVOCATION PHASE), they used a temporary list containing the pseudonyms of revoked vehicles. What's the difference between their temporary list and the CRL?


texts: What effect does a salt have on attacks against hashes's fundamental properties?

texts:
I am interested in analyzing how adding a salt to our hashed passwords affects the three types of attacks we can use. The three types of attacks against hashes are as follows:

We have the hashed output and we are looking for a matching input (pre-image).
We have an input (and implicitly the output) and we want to find another matching input (second pre-image).
We have the input and we want to find ANY output (collision).

My thought is that the addition of a salt to our output would only affect our ability to perform attack 1, because we are reliant upon the output to find a matching input. With the salt, our chances of finding a matching input becomes almost impossible because we have to check each output with every possible salt. Essentially, attack 1 is what's known as using a rainbow table.


texts: What's the difference between compromise and corruption in MPC?

texts: What is the difference between corruption and compromise? Are Compromising a user and corrupting a user same?


texts:
Recently a company called Bitcasa demonstrated a product of cloud storage. they indicated that they would use "Convergent Encryption" to secure your data and de-duplicate, essentially one copy of the same file between users.

From what I can read on a university paper about Secure Data Duplication which makes mention of "Convergent Encryption" and assuming this is what this is referring too.

My question is, what security implications of using this technology and is it truly secure that you cannot get the key based on chunk data being used to generate different keys between users.

Reference interview on Washington post


texts:
I want to use MAC as an additional protection of UDP-server from DoS attacks.
I prefer to keep MAC as short as possible and I assume 32 bit is good enough for this purpose.

I'm going to make it based on some well-known MAC (e.g. KECCAK Message Authentication Code)
Is it bad idea to use CRC32 of this MAC?
Or it is better to use first 4 bytes of MAC?


texts: Learning with Error (LWE) problem seems like a generalization of Learning Parity with Noise (LPN) problem, where in the latter one uses bits. But, this also makes LPN seem very related to the problem of decoding a random linear code. I was just wondering whether LPN is equivalent to the problem of decoding a random linear code? And whether there are some positive or negative results about the equivalence of LPN and LWE?


texts: Do any one-key-of-many cryptographic schemes exist?

texts:
I'm pretty sure I understand how public/private key cryptography works. Anybody can encrypt a message using a well-known public key, but only the person who holds the private key can decrypt it.

My question concerns securely sending a message to multiple people. Say there are n public/private key pairs. Is there a way to encrypt a message using the n public keys such that any one of the private key holders can decrypt the message in its entirety, but nobody else can?

Further, unrelated to public/private key cryptography, is there any scheme where there are n shared keys such that anybody who knows the n keys can encrypt a message such that any one of the shared keys can decrypt the message in its entirety, but nobody else can?


texts: Cryptography - Perfect secrecy => adversarial indistinguishability - proof

texts:
I'm just starting out with cryptography now and have gone over the various defnitions for a perfectly secret cipher. One of the equvilant definitons is adversarial indistinguishability. When trying to prove the equivilance I had a bit of trouble with one of the directions and ended up finding this proof online:

(Source: http://goutampaul.com/wp-content/uploads/2015/09/lecture4.pdf)

What I don't understand is where they use their inital assumption that the system is perfectly secret. Could someone point it out please?

And am I right to assume that the second C0 in each row at the bottom section is supposed to be C1?


texts: Do group signatures have unforgeability against the manager?

texts:
According to Wikipedia, Group Signatures unforgeability means only members of the group can create valid group signatures. What I am not clear on is whether that means the manager is also unable to create signatures on behalf of any members of the group.

Are there group signatures where the manager gives out the secret keys, or it is split to another party, but there's no way for them to forge signatures?
Is the manager usually assumed to be trusted in some way, maybe he can't be corrupted so secret keys of group members can never be learned?


texts: Comparing different hashes to confirm they came from the same string

texts: Is there any safe hashing algorithm that returns a different hash each time (like bcrypt) but has the possibility to compare 2 different hashes and determine that they were hashed from the same password/string without knowing this password/string?


texts: What methods allow us to determine the language used in a monoalphabetic substitution cipher?

texts:
Working on a cipher (which I assume to be a mono-alphabetic substitution cipher due to the letter frequency) I struggle with the fact that I don't know which language the plain text is written in. Looking at the letter frequency only, gives some hints, at least to exclude some languages, but far from pointing out one. I have also studied the index of coincidence, but several languages are quite close to each other and I am uncertain how much I can trust this.

Both these ways indicates that my particular cipher isn't written in English. It's also a patristocrat (no separations between words), which makes word-matching harder.

My question is: what methods are there, and which one tends to produce optimal results?


texts: Can we construct a simulation sound NIZK (Non Interactive Zero-Knowledge) proof?

texts:
A single theorem adaptive non-interactive zero-knowledge proof (P, V) for a language L is a proof system that satisfies

Completeness: If a string $x \in L$ (and P has the witness), the verifier V will accept with high probability.
Soundness: If $x \notin L$, the verifier V rejects with high probability.
Zero-knowledge: there exists a simulator M on input $x \in L$, outputs the ensemble which is computationally indistinguishable with the output of the protocol.

Since it is adaptive, $x$ is chosen based on the common reference string.

Single theorem implies that a common reference string is used to prove a single theorem $x$. If we use same string to prove more than one theorem, zero-knowledge property may not be preserved.

Simulation soundness is defined as given a list of simulated proof's to the adversary, adversary should not be able to produce a valid proof for any theorem $x \notin L$

If there exists a single-theorem adaptive NIZK, can we construct a simulation sound NIZK?


texts: Relation between key size and PRNG state size

texts:
Some (supposedly) cryptographically secure PRNGs have an internal state of only 160 bits or less. When the algorithm is otherwise properly designed, that seems like enough to generate a 128 bit key for e.g. AES.

Can the PRNG also be used for the generation of longer keys, e.g. RSA keys with 1024 bits?

My intuition is that it would take (on average) a brute force attack of 2^159 key generations to find the same key, which is probably harder than factoring the 1024 bit key (according to various key length comparisons).

Is there an easier way to crack an RSA key generated using such a PRNG? The OpenSSL PRNG documentation states that an internal state of at least 4096 bits is required to securely generate an RSA-4096 key; that would contradict my intuition.


texts:
I have been reading a paper where they construct probabilistic IO (indistinguishability obfuscation) from sub exponential IO. I want to know if the following two notions of sub-exponential security equivalent?

A scheme is sub-exponentially secure if a PPT adversary doesn't get more than 1/subexp(x) advantage.
A scheme is sub-exponentially secure if an adversary with sub-exponential computational power doesn't get more than negligible(x) advantage.

(x is security parameter)

The paper defines sub exp secure as defined in 1. But I have come across several notions where they define definition 2 for sub-exponential secure scheme.

Please clarify if both are equivalent. If yes please let me know the proof. If not then where does the equivalence fail?


texts:
Can you construct a key agreement system from public-key-encryption system? If so, how?

What about vice versa?


texts: Is XEX/XTS good for deterministic file encryption?

texts:
My understanding about XEX/XTS mode is limited. But from what I see, it has two good properties:

It is length-preserving so that encryption doesn't cost additional space.
It is deterministic, which is (usually bad but could be) a requirement in some use cases.

Assuming space is a scarce resource, encryption must be deterministic, while authentication is unnecessary, would XEX/XTS mode be a great choice for normal file encryption?

(A file is a byte stream, but we can impose offset-based virtual sectors on the stream and use these sector numbers in XEX/XTS algorithm.)


texts:
When Argon2, Balloon, scrypt, bcrypt¹, PBKDF2… are used for a password, we can call them password hash (for password storage) or password-based key derivation function (for use in encryption).

But that might not be understood when the context involves no passwords. Purposely-slowed hash is more descriptive, but awkward, and I have seldom seen it.

Are there established alternatives? If not, what do you propose?

Addition: I wish the term would be usable for strengthening the $b$-bit hash of a $3b$-bit Schnorr signature against brute force preimage attack. In this usage, there's nothing secret involved.

¹ As rightly pointed in comment, bcrypt can only produce 192 bits of output, which makes is passable for password hashing or short keys, but not a general Key Derivation Function.


texts: How to make a hypothesis test for a simple statistical test for a certain RNG?

texts:
I'm self-studying about hypothesis test in the context of RNGs.  I'm building a hypothesis test from scratch.  I'm taking the simplest statistical test I can think of: how many $1$s are there in the sequence sample?  My null hypothesis is that the RNG is uniform, so I expect the average number of $1$s to be close to $n/2$, where $n$ is the size of the sample.

I believe (or I guess) the sample averages should follow a normal distribution.  To implement the hypothesis test, I will have to know the variance, though.

What should I do here?  Should I look at a good RNG and come up with a variance relative to my simple statistical test?  This makes sense to me.  A good RNG will likely present averages close to $n/2$, specially if $n$ is large.  I could then empirically determine the variance this way.

Is there anything wrong with this construction?  Can you advise?  My main interest is not in testing real world RNGs.  My main interest is in knowing how to do hypothesis test, but I'm looking for an example in this precise context.


texts: zk-SNARKs vs. Zk-STARKs vs. Bulletproofs: definitions

texts:
I have become quite familiar with Bulletproofs the last few months. Bulletproofs is the name given to a zero-knowledge proof system for arithmetic circuits, by Benedikt Bünz et al. It is a specific protocol with specific properties.

When Bulletproofs are discussed, they are often contrasted with zk-SNARKs and zk-STARKs. See, for instance, this question on the Ethereum StackExchange, where they discuss properties of Bulletproofs and compare them among zk-SNARKS and zk-STARKs.

A zk-SNARK is a zero-knowledge succinct non-interactive argument of knowledge. A zk-STARK is a "scalable transparent argument of knowledge", according to Eli Ben-Sasson's "Scalable, transparent, and post-quantum secure computational integrity".

To me, it sounds like the comparison ends there: the papers I consulted until now refer to SNARKs and STARKs as a list of properties that a proof system should have, not as a specific instantiation of a proof system. Considering the aforementioned Ethereum.SE question, it seems like both zk-SNARKs and zk-STARKs are actual instances of proof systems, since they list specific complexities and timings. Papers about specific SNARK and STARK construction, e.g. the Ben-Sasson paper, all seem to refer to "previous S[TN]ARK contructions", making me wonder whether the Eth.SE comparison can be fair.

So my question(s) is/are:

What is a zk-SNARK:

a specific proof system, and if so: which one?
a class of ZK proof systems, and if so: is this class specific enough to claim that proofs are "always 200 bytes"?

The same for zk-STARK, with most probably the same answer.
I feel that question 1. will come down to a class of proof systems, which makes me wonder why Bulletproofs wouldn't be a "zero-knowledge, succinct non-interactive argument of knowledge"; they are typically considered separate.


texts: Compute Modulo exponentiation with prime powers

texts:
The problem is to find x such that

$$x = M^d \mod p^2$$, where M and d are large numbers, and p is
a large prime. Ideally we only want to compute $M^d\mod p$ and then use the result to further figure out $x$.

I know how it can be done if M^d is small, e.g. using The Lifting Theorem
However, in the problem mentioned, we do not want to compute M^d completely. So
it is not clear that this theorem is useful.


texts: Finding length of a key for a given vigenere cipher using Index of Coincidence


texts: AES GCM symmetric encryption of data at rest in c#, ciphertext much longer than plaintext

texts:
I've written encryption/decryption routines using AES GCM. Code can be found here.

I recently realized that the cipher text is longer than I believe it should be. It should add the tag and IV onto the encrypted plaintext, but the result is still longer than it should be.

Here is the portion of the code doing the encrypting

    using (MemoryStream ms = new MemoryStream())
            {
                using (IAuthenticatedCryptoTransform encryptor = aes.CreateAuthenticatedEncryptor())
                {
                    using (CryptoStream cs = new CryptoStream(ms, encryptor, CryptoStreamMode.Write))

                    {
                        // Write through and retrieve encrypted data.
                        cs.Write(message, 0, message.Length);
                        cs.FlushFinalBlock();
                        byte[] cipherText = ms.ToArray();

                        // Retrieve tag and create array to hold encrypted data.
                        byte[] authenticationTag = encryptor.GetTag();
                        byte[] encrypted = new byte[cipherText.Length + aes.IV.Length + authenticationTag.Length];

                        // Set needed data in byte array.
                        aes.IV.CopyTo(encrypted, 0);
                        authenticationTag.CopyTo(encrypted, IV_LENGTH);
                        cipherText.CopyTo(encrypted, IV_LENGTH + TAG_LENGTH);

                        // Store encrypted value in base 64.
                        return Convert.ToBase64String(encrypted);
                     }
                 }
             }

Here are two examples of the encryption:

plaintext: example

ciphertext: XtmTBIqKxKdYKWH2zXRUp8jN6etGNUiTyffAFZYV3KB2WVU=

plaintext: much longer example, blah blah blah blah blah

ciphertext: H17hnG4CSmZQ0UeEcY6wirtjW1il+dw7JHqXwWm908Tvb8/+q0E1HerN0chbuUbhL0jLOs8HIpp7ypQQ/ LTacnWW22CyiwAuiA==

The IV is 12 bytes. And I believe the authentication tag is 16 bytes. Why is the cipher text coming out so much longer than expected and how should I fix this issue?
Thank you.


texts: Is it possible to encrypt data in such a way that it cannot be decrypted with the key used to encrypt it but can be decrypted with another key

texts:
I'm very new to cryptography and encryption so I apologize if the answer to this is well known, but I can't find anything in my research.

The crux of the problem is the need to store data on an offline device which cannot be trusted. Is it possible to encrypt the data in such a way that it cannot be read by the device that encrypts it, but can be read by a server that the device later uploads the data to?

The device can communicate with the server before going offline and capturing data so an exchange of keys can take place before any data is encrypted if that helps.