texts: Feistel cipher vs Substitution-permutation network - number of rounds

texts:
So I have been doing for the last couple of days comparison between Feistel cipher and Substitution-permutation network. Now I can say I know a lot about them and their similarities and differences but there is still one more thing I would like to know and I can't find it anywhere.

The thing is I don’t know how many rounds these structures have. I mean simply which structure has more rounds and why?

After searching a lot for this I have a feeling (didn't find any hard proof) that we can customize number of rounds when designing a symmetric algorithm based on one of those structures, if this is true then I want to know on which structure based algorithms has typically more rounds (or how many rounds they need to have to be considered safe)?


texts:
Let $F : \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n $ be a PRF. And let the encryption function be $Enc{_k}(m) = r\mathbin\| (F{_k}(m\bigoplus r)$ , r being a random value.
Im trying to proof that this scheme is not CCA-secure, however I'm already failing at finding a correct decryption. Since a PRF is not invertible, how is it possible to recover the $m$ from the ciphertext?


texts:
In CTR mode encryption, the encryption block is not required to be invertible. Thus, a PRF can be used instead of a PRP. However most of the implementations of CTR mode are based on AES which is a PRP.

This made me think if we can have a PRG as the encryption block where the (key || counter_i) can be supplied as a seed.

If we use a secure PRG such as SALSA20 instead of AES, do we achieve a secure CTR mode encryption?


texts: Prove how to brute-force the double encryption with complexity 2^57 rather than 2^112?

texts:
We know that DES has key length that is too short to defend brute-force attack. One idea to
improve DES was to encrypt a message using DES twice with two different keys. Let E be the
encryption algorithm of DES and k1, k2 be two DES keys. Such a double DES encryption performs
like
c = E(k2; E(k1; m))
We might hope now the total key length is 112 bits, enough for defending brute-force attack which
should take 2112 steps. It turns out, such a system doesn’t provide that level of brute-force security.
Given one pair of plaintext-ciphertext pair, show how to brute-force the double encryption with
complexity 257 rather than 2112.
This attack demonstrates that double symmetric ciphering doesn’t increase the security much.
In fact, To get 112 bits security, Triple-DES (a.k.a 3-DES) was introduced and standarlised. You
will see that in many security protocols, 3-DES remains an option.


texts: Speeding up quotient determination in high-radix montgomery modular multiplication

texts:
In this paper Simplifying Quotient Determination in High-Radix Modular Multiplication, the authors have proposed to replace the original modulus $M$ in Montgomery Multiplication $ABR^{-1} \bmod{M}$ to a new value $\tilde{M} = (M' \bmod{2^k}) M$, where $(-MM')\bmod{2^k}=1$.

The new modulus $\tilde{M}$ is used to improve the original Montgomery multiplication algorithm but also gives an output in the range of $[0, 2\tilde{M})$ instead of the range $[0, 2M)$ I actually need. However, the paper does not mention how to convert the result back to the desired range. What should I do to retrieve the actual result of $ABR^{-1} \bmod{M}$?


texts: Statistical closeness implies computational indistinguishability

texts:
This is so trivial that authors usually don't bother to give an explicit proof. But for me there is some vagueness.

We say that two ensembles $X_n$ and $Y_n$ are statistically close, if
$$ \Delta(n) = 1/2 \sum_{\alpha}|\mathbb{P}[X_n = \alpha] - \mathbb{P}[Y_n = \alpha]| $$ is negligible in n. The probability is taken over the randomness of $X_n$ and $Y_n$ respectively.

We say that two ensembles are computationally indistinguishable if for every PPT-adversary D we have
$$ |\mathbb{P}[D(X_n) \to 1] - \mathbb{P}[D(Y_n) \to 1]|$$
is negligible.

Why the former implies the latter?

I do understand that for every deterministic function $f$ we have
$\Delta(f(X), f(Y)) \le \Delta(X, Y),$ where $\Delta(\cdot, \cdot)$ is the statistical distance.

But in the case of PPT adversaries $D$ is not deterministic, there are implicit random coins. Why can we treat PPT-algorithm $D$ as deterministic function?


texts:
My question maybe will be stupid, but my problem is that I do not understand why stream ciphers need a key and also a nonce. As far as I understand, the keystream is generated with the nonce. The same key can be reused with a different nonce.

Wouldn't be simpler just to use a new key each time? If I understand good, to decrypt the message the recipient needs the nonce. Is communicating the nonce simpler than communicating the key?


texts: (How) Is DDH generally broken in groups of composite order?

texts:
In a somewhat recent lecture a claim was made that I couldn't back up myself but it got me curious whether it actually holds:

  If the order of the group is not prime, then the DDH assumption does not hold.

So my question would simply be:
How does one break DDH in general assuming only that the group order is composite? Or is there a group with composite order where DDH is conjectured to hold?

My research only lead to the special case of $\mathbb Z^*_p$ which has composite order as $p-1$ is even which leads to exploitable attacks on ElGamal thanks to the Legendre Symbol containing useful information which breaks DDH because ElGamal is proven CPA-secure iff DDH holds.


texts: Does every language's SHA256 implementation provide different result for the same value

texts:
Probably this is very naive question, based on lack of understanding but I was watching a video from Andreas M. Antonopoulos about blockchain, bitcoin and consensus algorithms and he asked for the SHA-256 output of the string Hello!. A guy told him the first few characters, and being Windows/C# dev I decided just for fun to check the answer implementing this very simple C# method:

    public byte[] Generate(string valueToHash)
    {
        byte[] hashValue;
        byte[] stringToBytes = Encoding.ASCII.GetBytes(valueToHash);

        using (SHA256 hashGenerator = SHA256.Create())
        {
            hashValue = hashGenerator.ComputeHash(stringToBytes);
        }

        return hashValue;
    }

and then output the result using this method:

    public static void PrintByteArray(byte[] array)
    {
        for (int i = 0; i < array.Length; i++)
        {
            Console.Write($"{array[i]:X2}");
            if ((i % 4) == 3) Console.Write(" ");
        }
        Console.WriteLine();
    }

But I got a different result.

I remember in the past that there were sites which were storing a huge databases of hashes and the actual value to produce them and back then it was possible to paste the hash value and if it's something common you will get the actual string. This got me to think that no matter what language/Os you are using, a value hashed with SHA-256 for example would produce the same result. However it seems that this is not entirely the case. The guy from the video who provided the answer turned out (from the comments) to use a Mac machine, so what exactly is causing the SHA-256 to produce different outputs for the same input? Is it the OS, is it the programming language? Maybe I've made mistake in my simple code?


texts: Why is it necessary a prime factor recovery for a RSA Key-Pair Validation (in case of fix public exponens)?

texts: In NIST 800-56B publishing, this is done with the $(p, q) = RecoverPrimeFactors (n, e, d)$ function. I don't understand why is necessary if $p$ and $q$ are known during in generation. In my opinion, validation without the RecoverPrimeFactors function checks the required criteria.


texts: Are block ciphers used in public key crypto?

texts:
I was reading about block ciphers and most articles state they are being used in symmetric key cryptography. Are they also being used in public key cryptography? if not, what alternative pkc use?

Thanks,


texts: Forward Security of Symmetric Encryption Schemes with LFSR based PRNG

texts: Forward security can be achieved using symmetric encryption schemes by combining with a pseudo-random number generator (PRNG). Does LFSR based PRNG provide forward security in this case?


texts: PBKDF2 can be used to derive a key from a passphrase, having in input the passphrase, the chosen number of iterations to slow down a brute force attack, a random salt and the chosen keylength. In its implementation it needs a PRNG which can be, for example, HMAC-SHA-something; but HMAC needs itself a key together with a "message" (which I think is the passphrase in the first iteration, and then its resulting hash in the subsequent ones): so what is this key?


texts: How would I go about solving this cipher?

texts:
I am not sure this is the right place to post this... recently I was given the following image by my friend in the context of a game we play together. Please note the characters at the bottom.

I would like to figure out what the characters say, but I am not even sure how I would go about it. I suspect it's some sort of cipher where each symbol represents one specific letter.

What techniques could I use to start trying to figure out what the characters say?


texts: How to use OpenSSL command line utility to encrypt data with encrypted key from public key?

texts:
I may not be asking the right question.  I am fairly new to data encryption.

I am currently being sent encrypted data that's stored as follows:
[
[keysize]
[key encrypted with public key]
[ivsize]
[iv]
[data encrypted with supplied key earlier in file]
]

To decrypt (in my C# code), I have to first read the key out.  I then decrypt that key using my certificate's private key.  Afterwards, I read the IV and use it with the newly decrypted key to decrypt the data using Rijndael AES decryption. (to note: it uses AES/CBC/PKCS7 padding)

This works great for receiving the encrypted data and decrypting it.  However, I would like to generate the exact same type of encrypted file they are sending me and have exhausted myself to the point of total confusion with my various trial and errors.  I was told by a colleague that this is a common encryption tactic.

I would like to know if it would be possible to generate the encrypted file using the openssl utility rather than writing code?


texts: IV Re-use and Chosen Plaintext against 56bit Blowfish (CBC)

texts:
I am looking at a very old protocol which uses Blowfish to encrypt packets with a constant 8-byte IV in CBC mode.

Assuming I have:

The ability to arbitrary encrypt known plaintexts
The IV

I know that this lets me identify which plaintexts begin with an identical block and lets me identify also which plaintexts are exactly identical (since the cipher texts will remain identical until the first divergent block).

Is there any information which IV-reuse might leak that could be used to reduce the brute-force space for a dictionary attack or otherwise learn additional information about the plaintext?

I know that there are several theoretical weaknesses in Blowfish (such as this reflection attack against weak keys) but I am not sure if IV-reuse makes it possible to identify weak keys with less data than the hundreds of gigabytes proposed in those attacks.


texts: Why does a hacker need to crack the key to an encrypted file, instead of just brute forcing the password?

texts: Most encryption softwares don't seem to have a trial limit. So why would a hacker need to crack the key, or even need to know the salt value, if he can just brute force the 6-8 digit password?


texts: Hashing with (some sort of) Public and Private keys/salt/nonce

texts:
I'm trying to design a protocol where hashing can involve some public and private components.
The idea is that Alice hashes a value with minimal computation and sends the hash to Bob.
For Bob it should be exponentially harder to re-create / verify the hash against a given value with the hash he received from Alice.

The hash function Alice is going to use will be something like this, with constant time:

$$H_A = \text{hash_generate}(\mathit{input}, \mathit{private\_component}, \mathit{public\_component})$$

The hash / verification function Bob is going to use will be something like this, with exponential time:

$$\text{hash_verify}(H_A, \mathit{input}, \mathit{public}\_component)$$

What I have devised is the following:

This is what Alice does, (this is constant time)

Alice creates random $n$ bits as $\mathit{public\_component}$
Alice creates random $n$ bits as $\mathit{private\_component}$
Alice salts the input with both components and hashes it, say $\text{SHA-3}(input \mathbin \| (\mathit{private\_component} \mathbin \| \mathit{public\_component}))$
Alice sends the $\mathit{public\_component}$ and the hash result $H_A$ to Bob

And what Bob does in order to verify is the following:

Bob creates random $n$ bits as (replacement) $\mathit{private\_component}^{rand}$
Bob salts the input with both components and hashes it, say $\text{SHA-3}(input \mathbin \| (\mathit{private\_component^{rand}} \mathbin \| \mathit{public\_component}))$
If the hash result is the same as Alice's hash result, he has verified it
If the hash result is the not same as Alice's hash result, goto 1 (or fail with a given repeat count based on $n$, guaranteeing we have done enough permutations to prove that we can't verify the hash)

So the expected complexity of Bob's operation should be around $\mathcal{O}(2^n)$

This protocol is what we have came up with; it's similar to proof of work in a way.

Are there protocols for such a use-case? If yes, how are they called?


texts:
Say I am hashing hashes (taking the hash of a previous hash) for an endless amount of time.

How many times would it take, on average, to fall into a loop when using SHA-2 (more specifically SHA-256 and SHA-512), like such:

original text = z (can be any string)
hash z = b
hash b = c
hash c = d

...

hash n = b (restarting loop)

or more literally,

original text = "test"
SHA-256 of "test" = "9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08"
SHA-256 of "9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08" = "7b3d979ca8330a94fa7e9e1b466d8b99e0bcdea1ec90596c0dcc8d7ef6b4300c"

...

SHA-256 of n = SHA-256 of "test" = "9f86d081884c7d659a2feaa0c55ad015a3bf4f1b2b0b822cd15d6c15b0f00a08"

How many attempts, on average, would this take?


texts:
Is the PCG family of PRNG algorithms cryptographically secure, and if not, what about them makes them inadequate for that?

I have a good enough understanding of the general problem space that if you mention something like "backtracking resistance" and give a sentence summary of what it means, I can connect the dots enough to understand why it matters for security.

I have a (likely incomplete) understanding of what it takes to make a cryptographically secure PRNG - for example I know that resistance to predictability or backtracking matters, ideally resistance that stays strong even as the attacker learns more outputs of the PRNG or learns bits of the PRNG's internal state.

But I lack the deep experience and knowledge needed to actually evaluate PRNGs myself to figure out if they meet any of these properties, or to be confident that I haven't missed something.

I do know that PCG was not designed to be suitable for cryptography - it seems to have been optimized for good statistical properties and efficiency of producing outputs.

I have also found people saying that PCG is not cryptographically secure.

But what I have not found is any actual analysis of PCG - any write-up explaining what properties it fails to fulfill, and so on.


texts:
I am doing an example on Weil pairings, and for that purpose I follow the thesis of Alex Edward Aftuck, The Weil Pairing on Elliptic Curves and Its Cryptographic Applications.

By following his thesis, on page #39 he selects 4 points on the elliptic curve  $Y^2=X^3+2X^2-3X$ and calculates six divisors from it
as shown in the figure:

Using divisors, he calculated four rational functions as  but in the last step, he calculates the Weil pairing between $P_1 $ and $P_3$. The sums of points are $P_3+S=(-2.496,-2.047) $ and $P_1-S=(20.798,-98.990) $.

My question is: how can I can put the points into the functions $f_{p_1} $ and $f_{p_3} $?  All of the functions have three variables $X,Y,Z$, but we have  only two points. What is the value of $Z$, and how can I calculate functions using these points? Please help me as I'm really confused.


texts: Zero-Knowledgeness of Fiat-Shamir heuristic

texts:
I have read about the Fiat-Shamir heuristic for making an interactive proof of knowledge into a non-interactive proof of knowledge. If I apply this to zero-knowledge proof of knowledge, it seems to me that I would destroy the simulator and therefore the zero-knowledgeness.

Does the Fiat-Shamir heuristic destroy zero-knowledgeness?
If it does, it it possible to circumvent this?

Link to Fiat-Shamir heuristic.


texts: Would using perfect S-boxes in F function of an unbalanced Feistel network produce a simple and secure cipher?

texts:
When I read some articles about cryptography on wikipedia, I took note of the following statements (please, correct me, if any of these are wrong):

Perfect S-box (based on bent functions) provides maximum possible
security against linear (and differential?) cryptanalysis.
The problem with using perfect S-boxes is that an S-box constructed
purely from bent functions can not be invertible.
F function in Feistel network does not have to be neither balanced
nor invertible. One could even make an extremely unbalanced Feistel
network, where one side is only one bit, and have a bent function used as F.

From these statements it seems that using perfect S-boxes in F-function of an unbalanced Feistel network is an obvious choice for a simple and secure cipher. I understand, that someone would have come up with this long ago, if it was indeed so simple, but I can not find any information regarding possible downsides of such design.


texts: Secure multi-party random number generation

texts:
This question is actually continuation of my previous one.

Secure multi-party computation for digital signature

to implement solution there, I have to generate random data for padding (I will use PSS).

There are N parties. Up to M are malicious adversaries (were trusted, but got taken over silently). I will be happy with solution for any N and M = 1.
Parties should send to each other some random data d[i] and each party based on all d[1..N] should generate some final random value R.

From one side, value should be one and the same for all parties, i.e. calculation should be a fixed predictable process and all parties should get one and the same value R. From another side, malicious adversary party should not be able to affect randomness of R[i], i.e. even malicious adversary should not be able to generate d[m] to get specific R.

Looks like I can achieve this by simply hashing all d[i] values in predictable order. For instance sort d[i] and calculate hash of "well-known-secure-prefix" + d[1..N] + "well-known-secure-suffix".

Am I missing anything?


texts: Benefit of capitalization when using Diceware passphrases?

texts:
If I use a Diceware generated passphrase of any given length, will capitalizing the first word (or any word for that matter) effectively double the number of combinations that would have to be tried in a brute force attack.  In other words by capitalizing one word of the passphrase chosen from a list of ~7500 words haven't I now created a single list of ~15K words: abc, def … xyz, Abc, Def … Xyz.

Even if I told an attacker which word list I used and that I capitalized the very first word of the passphrase, wouldn't the random nature of the dice throw create a larger space to search through before a successful guess?


texts: Paillier encryption problem when q or p divides r

texts:
I am having a problem with Paillier encryption as described on Wikipedia.    It says to pick $0 < r < n$, where $n=pq$ for large, equally sized primes $p$ and $q$.  However, I've been testing this under trivial key sizes, setting p=11, q=13, and encrypting m=1.  When I try all legal values of r, I find that decryptions fail when $p | r$ or $q | r$.

(To be clear, I'm doing the gcd checks and seeking a random generator less than $n^2$, not using the "simpler variant" on the Wiki page although I have tried that, too, without success.)

I've seen a particular Paillier implementation in Python in which the random value of $r$ is chosen to be a prime number, maybe to avoid this problem (I asked about it in this thread), but I see no such specification of a restriction on this randomness constant in the Wikipedia page or the original Paillier paper.

What am I doing wrong?  If it's appropriate to post ~40 lines of Python code on this forum, I will - please indicate in a comment.  I don't want to junk up the feed.

If this is a theoretic problem, what is a good limit to avoid choosing an r that is a multiple of p or q, without revealing knowledge of p or q to the party doing the encryption, (gcd with n is 1,) or is it just based on the law of large numbers that the sender will never land on such an r in practice?

Thank you.


texts: ECDSA, EdDSA and ed25519 relationship / compatibility

texts:
I'm trying to understand the relationship between those three signature schemes (ECDSA, EdDSA, and ed25519) and mainly to what degree they are mutually compatible in the sense of key-pair derivation, signing, and signature verification. But I was not able to find any conclusive information. I mean, for example, can you verify ed25519 signatures with EdDSA and/or vice versa?
I found the best info here from which I got the suspicion that there might be some compatibility between those schemes, but I could not find any source to prove or disprove it.
Could somebody shed some light on this?


texts:
What is the noise in homomorphic encryption schemes? (or where does the noise come from, I see that its inbuilt in the scheme and is not a side channel or disturbance noise)

Is it also due to the noise that HE is a probabilistic scheme ?


texts: Reference for the Tortoise and Hare algorithm by Floyd?

texts:
Can someone please point me to a book or paper that describes the Tortoise and Hare algorithm by Floyd?

I know there are ample websites out there, but for reference purposes, I need a book or paper to point to.


texts: Post-quantum authenticated key exchange with forward secrecy

texts: Are there any post-quantum, forward-secure, hybrid, optionally authenticated key exchange protocols?  Specifically, I am looking for one that can be deployed in a hybrid with X25519 + EdDSA.


texts: Can you help with that definition for a CCA?

texts:
The following is a definition taken from Introduction to Modern Cryptography by Katz and Lindell.

I'm having a hard time understanding some basic concepts! Can you please help me?
$\newcommand{\Gen}{\operatorname{Gen}}\newcommand{\Enc}{\operatorname{Enc}}
\newcommand{\Dec}{\operatorname{Dec}}$

  Consider the following experiment for any private-key encryption scheme
  $Π=(\Gen,\Enc,\Dec)$, adversary $A$, and value $n$ for the security parameter.
  The CCA indistinguishability experiment PrivK:Aan (n) is:

  A key $k$ is generated by running $\Gen (1^n)$.
  The adversary $A$ is given input $1^n$ and oracle access to $\Enc_k (·)$
  and $\Dec_k (·) $. It outputs a pair of messages $m_0, m_1$ of the
  same length.
  A random bit $b\in \{0,1\}$ is chosen, and then a ciphertext
  $c = \Enc_k(m_b)$ is computed and given to $A$. We call $c$ the
  challenge ciphertext.
  The adversary $A$ continues to have oracle access to $\Enc_k (·)$ and $\Dec_k (·)$,
  but is not allowed to query the latter on the challenge ciphertext itself.
  Eventually, $A$ outputs a bit $b'$.
  The output of the experiment is defined to be 1 if $b' = b$, and 0 otherwise.

In the second bullet point what does "It outputs a pair of messages" mean? Who and where does it output those messages? Does the adversary output the messages? The oracle?
What's the purpose of the random bit b?


texts: Smallest Guaranteed hash collision cycle length

texts:
If I take the sha-256 of an empty string, and apply the hash function $2^{256}!$ times, will I end up with the same hash that I started with?

Is the smallest required cycle equal to the LCM of $1$ to $2^{256}$?


texts:
I'm looking through the test and examples of libsnark, let's take for example here:
https://github.com/christianlundkvist/libsnark-tutorial/blob/master/src/test-gadget.cpp
at line 19 there's:
  default_r1cs_ppzksnark_pp::init_public_params();

Is this the step that generates the toxic waste?

If so, then the same protoboard is used to generate the verification and proving keys, but then also to create the proof:
  const r1cs_ppzksnark_proof<default_r1cs_ppzksnark_pp> proof = r1cs_ppzksnark_prover<default_r1cs_ppzksnark_pp>(keypair.pk, pb.primary_input(), pb.auxiliary_input());

but shouldn't the prover and the generator be different entities? On the other hand, if I look into the initialisation (init_public_param) in the end I end up in the definition of public_params for curves in libff:
https://github.com/scipr-lab/libff/blob/master/libff/algebra/curves/public_params.hpp
which is just a list of templates, there's nothing private about it.

How should the generator step be separated from the prover step?

The prover has everything (public and private info), so he can indeed generate the circuit from scratch, but the verifier should "not" accept the keypair from the prover, correct?

Finally, the generator (who knows everything, public and private info) prepares the keys, sends them to the prover and the verifier. The prover constructs its own pb (protoboard) because he needs the pb.primary_input() and pb.auxiliary_input() to create the proof, then uses its own pb with the generator's proving key to generate the proof. In my experiments the keys generated by the generator and by the prover are the same even if I initialise 2 different pbs, this is counter intuitive to me because the prover can impersonate the generator. Are the keys the same because the init process of the protoboard is the same?

Thanks for anyone who read this far! Any hint is appreciated
T.


texts:
Just a small question. Since in LWE the error is rather small, is there a problem with replay attacks? What I mean is that if we use the typical scheme of Regev [1] to encrypt a vector m, but this vector is sent, e.g. 1000 times, then an eavesdropper may perform a simple voting scheme to approximate the original message. Am I losing something?
References:
[1] Regev, Oded. "On lattices, learning with errors, random linear codes, and cryptography." Journal of the ACM (JACM) 56.6 (2009): 1-40.


texts: How do I find out whether a message in CBC has padding?

texts:
When a program is decrypting a message encrypted by CBC mode, what does it find out, whether the last bytes of the last block is part of the padding or part of the plaintext?

Example: Use CBC mode with 4 Byte blocksize and encrypt the following two messages:

m1 = ABCDEF
m2 = ABCDEF22

M1 gets padding and will be "ABCDEF22". How do I find out, whether the original plaintext was ABCDEF, or ABCDEF22?


texts: Genuine encryption from only one source?

texts:
Is there any technique so that if I encrypt data, the ciphertext would be genuine and if someone else tries to encrypt the same data the ciphertext could be determined as fake or just invalid?

I want to create a network in which the user has to register to get a ciphertext (like a token) and only after getting a genuine ciphertext would they be allowed to communicate with other users in the network. The ciphertext would contain their identity.

However, if I simply use any simple encryption method, the user would be able to fake their identity by encrypting the data in the same format and method. I do not want to use a server/database to verify the identity. That is why I was thinking of ways to disallow fake ciphertexts.

If this is possible can you suggest a solution to achieve this? If not can you suggest an alternative?


texts: Computationaly efficient distinguisher for a PRP generator

texts:
Let $n$ be an integer (the motivating context had $n\approx2^{27}$). All other lowercase variables are non-negative integers less than $n$ (elements of $\mathbb Z_n$). All uppercase variables are vectors of $n$ distinct such elements, or equivalently permutations of $n$ elements.

We want to efficiently distinguish among oracles, with as few queries as possible, in an experiment where an oracle initializes, then at query $j$ outputs a permutation $V_j$, with the additional property that: $\forall i,\forall j,\forall k,\;j\ne k\implies V_j[i]\ne V_k[i]$.

Oracle 1 initializes with an empty memory of earlier outputs, then at each query outputs a random permutation uniformly distributed among those still allowed by the additional property.
Oracle 2 initializes by choosing 3 independent random uniformly distributed permutations $P$, $Q$, $R$; then computes $V_j[i]$ as $R[(P[i]+Q[j])\bmod n]$.

Both oracles meet their duty and can answer $n$ queries. Each of their output, taken in isolation, is indistinguishable from a random permutation. The scheme of oracle 2 and standard Format-Preserving Encryption techniques allow to build a PRP generator meeting the additional property, with $O(\ln n)$ memory, and direct access to any output value.

By a counting argument, for $n>4$, a distinguisher is possible with 3 queries if we disregard efficiency. But how can we build an efficient distinguisher?

Any proposal for an efficiently implementable oracle 3, harder to distinguish from oracle 1?

Additions:

As pointed by David Cary, what's constructed is known as a latin square. Terry Ritter has a literature survey, and discussions on their uses in cryptography. See also Smile Markovski Design of crypto primitives based on quasigroups in Quasigroups and Related Systems, 2015.
Possible application: decide how to lend to participant $i$ out of $n$, on week $j$, sample number $V_j[i]$ out of $n$, in a randomized manner additionally such that no participant gets the same sample twice. In that practice, permutations can be implemented as ciphers using Format Preserving Encryption.
Proof that Oracle 2 has the additional property: If $j\ne k$, then (since $Q$ is a permutation, thus injective) it holds that $Q[j]\ne Q[k]$, thus $((P[i]+Q[j])\bmod n)\ne((P[i]+Q[k])\bmod n)$, thus $R[(P[i]+Q[j])\bmod n]\ne R[(P[i]+Q[k])\bmod n]$, thus $V_j[i]\ne V_k[i]$.


texts: I see Chacha20Poly1305, XsalsaPoly1305 and AES GCM usually used and mentioned in literature and implementations as AEAD cyphers. My question is that Poly1305 provides authentication and Salsa20 provides encryption, a combination of both can be considered AEAD or not? Even though it is not a standard, does it technically fit the definition of an AEAD?


texts:
I'm developing a security/encryption software and I'm using AES CFB (block size: 16 and key size: 32 bytes).

I want to know, if I also keep IV (32 bytes) secret like the key itself (32 bytes), would it add to security or not?

Encryption key and IV will not be specified by user, it will be generated and then encrypted with RSA and stored in safe storage. So I'm thinking to generate randomly key and IV. So if I also keep IV and key (both generated) in secure place would it make my crypto stronger or it's preferred to make IV constant in my application code?


texts: What happens if the first input block is identical to the key in DES?

texts:
In Data Encryption Standard (DES),
M is the input message and K is the key of 64 bits size.
M is divided into n 64 sized blocks (B1,B2,B3...Bn).


texts: Asymmetric algorithm for one time signing of small cleartext

texts:
I want to generate a key pair such that the private key can be used once to sign a small message (1024 bytes) at some indeterminate point in the future and the public key can be used to verify that signature, what can I do to get better security than a regular asymmetric algorithm (e.g. RSA)?

The use case is allowing a user to "revoke" data by bundling the public key with the data. The user can then publish a revocation message (which can also contain some arbitrary but short message) with the private key.

And, do these requirements make any of the post-quantum algorithms especially suitable?


texts:
My question is about chaining two hash functions to create a robust combiner
for preimage resistance. @Zooko already gave a detailed answer here:

  $$H_{\circ}(x) = H_0(H_1(x))$$

  is as strong as the strongest of its two components.

However, in the comments below, @Arno Mittelbach showed the idea was dangerous: if $H_0$ is a random oracle and $H_1$ is a constant function (that maps every input to $0$), $H_{\circ}(x)$ is a constant function. However, he did not address @Paŭlo Ebermann's construction

  $$H_{\circ}(x) = H_0(H_1(x)|x)$$

  ...to have the improved preimage resistance, while still not having more collisions than with only one hash.

when $H_1$ is constant function, @Paŭlo Ebermann's construction

$$H_{\circ}(x) = H_0(H_1(x)|x) = H_0(0|x)$$

appears to be indifferentiable from a random oracle. However, I understand it might be impossible to know which function is the constant function. If it's $H_0$,

$$H_{\circ}(x) = H_0(H_1(x)|x) = 0$$

So I'm wondering if this knowledge gap can be remedied by using construction

$$H_{\circ}(x) = H_0(H_1(x)|x) \oplus H_1(H_0(x)|x)$$

In that case if $H_1$ is a constant function

$$H_{\circ}(x) = H_0(0|x) \oplus 0 = H_0(0|x)$$

On the other hand, if $H_0$ is a constant function

$$H_{\circ}(x) = 0 \oplus H_1(0|x) = H_1(0|x)$$

Is there any downsides to this construction outside speed? I understand it does not distribute trust on collision resistance, that is okay considering my use case.

Also, I'm unsure if this paper applies to my construction as one of my hash functions is Blake2 and another is SHA3-256 (which is wide-pipe sponge function, not MD/HAIFA). To my knowledge it was also the case none of the attacked constructions in the paper were against constructions that contained chained hash functions.


texts: Is this authentication system insecure or not

texts:
So I want to create a simple, fast and yet secure authentication in two steps for a PC - microcontroller communication.

The first step is a seed request, the second step is an authentication request.

The encryption that is being used is AES-128.

There should be a fixed key k with a length of 16 bytes.

Whenever a seed request is coming a random 16 bytes authentication message m should be generated and then be encrypted with k and sent back to the client as a seed s.

(NOTE: E(k, m) will always output the same s)

The seed s then should be decrypted with k by the client and then the original authentication message m should be sent to the server as an authentication request.

The server compares the auth message m with the message of the request, and grants access if they are equal or rejects the request otherwise.

Also assume that an adversary can collect as many m and s pairs as he wants.

Based on the information above is it feasible to easily break this system or not?


texts: Design of MixColumn Transformation in AES

texts: Why is the multiplication in MixColumn Transformation particularly by 2,3,1,1 cyclically? Why not some other numbers?


texts: Is there any hash function that relies on integer exponentiation instead of XOR?

texts: I'm trying to implement a hash function in an esoteric language that has no 32-bit or 64-bit operations. Keccak, for example, is too slow in that language. I'd need a design that minimizes the number of 1-bit operations. Alternatively, I could also use a hash function that relies on integer exponentiation, which is not expensive on this language. Is there any hash function like that?


texts: Is there a way to create an encrypted email with no third party application

texts: I would like to send and receive emails between group of people. Is there a way to create it with no need to use some other 3rd party application. Is there a way just to transfer files between 2 people so there won't be any way to decrypt it by any other technology?


texts: Oblivious transfer impossible from noiseless channels

texts:
If computationally unbounded parties $A$ and $B$ have only a noiseless channel between them, why is information-theoretic oblivious transfer impossible even for the passive cheating setting?
Intuitively, the noiseless channel makes the views of $A$ and $B$ almost identical except for the private randomness that $A$ and $B$ use. An unbounded passive cheater shouldn't be able to guess this randomness. How do we provably rule out some clever usage of private randomness that allows the sender to hide one of their bits and the receiver to hide her choice bit?


texts: how to validate cert when signed cert has authority key id but signing cert doesn't?

texts:
Say I have the following signing cert:

-----BEGIN CERTIFICATE-----
MIIB4zCCAUygAwIBAgIUSyCTib61O8k8TM5JA5n3zDYDFs8wDQYJKoZIhvcNAQEF
BQAwHDEaMBgGA1UECgwRcGhwc2VjbGliIGRlbW8gQ0EwIBcNMTcxMjEwMTYxMDIw
WhgPOTk5OTEyMzEyMzU5NTlaMBwxGjAYBgNVBAoMEXBocHNlY2xpYiBkZW1vIENB
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCn5XdGJUd9PY9zpksbJ2kD57PL
nQ3ISK+qbeSe2H+Uj0AEDnm611tvXlr9a7zBPNwZ2ali9bczirQkxtu/sftSHCGv
LL6sz1vdYP0Un792o5h+PkbQLnDe1lf/W8Q87GY9cRxUQVVfA7QUfgsl4iWgi7tv
qz3dRmxzBpjpgWvp/QIDAQABoyAwHjALBgNVHQ8EBAMCAQYwDwYDVR0TAQH/BAUw
AwEB/zANBgkqhkiG9w0BAQUFAAOBgQBQJpF/uakVjNIOz4Ve+duZYeeghpVxVNVK
t4OFi8DQzAsdFBpDDg/ZdAoXYOI/VHwNR+jKS2bPLmvNR2dP+OuZVdSTYu4/dZtI
Tp9ju17bym9oyWjX8CApa32+4N4WtcYLaVHOgyGA9f1VRHBtLTc8xcuHnJg6v3m9
TYVkR8c3IQ==
-----END CERTIFICATE-----

Here's the output of openssl x509 -in mycert.pem -text -noout on that cert:

Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number:
            4b:20:93:89:be:b5:3b:c9:3c:4c:ce:49:03:99:f7:cc:36:03:16:cf
    Signature Algorithm: sha1WithRSAEncryption
        Issuer: O=phpseclib demo CA
        Validity
            Not Before: Dec 10 16:10:20 2017 GMT
            Not After : Dec 31 23:59:59 9999 GMT
        Subject: O=phpseclib demo CA
        Subject Public Key Info:
....
        X509v3 extensions:
            X509v3 Key Usage:
                Certificate Sign, CRL Sign
            X509v3 Basic Constraints: critical
                CA:TRUE
    Signature Algorithm: sha1WithRSAEncryption
....

And the following signed cert:

-----BEGIN CERTIFICATE-----
MIIB5TCCAU6gAwIBAgIUVCrbYZRButS1ka5fyUe2iOzFAmwwDQYJKoZIhvcNAQEF
BQAwHDEaMBgGA1UECgwRcGhwc2VjbGliIGRlbW8gQ0EwIBcNMTcxMjEwMTYxMDIw
WhgPOTk5OTEyMzEyMzU5NTlaMB4xHDAaBgNVBAoME3BocHNlY2xpYiBkZW1vIGNl
cnQwgZ8wDQYJKoZIhvcNAQEBBQADgY0AMIGJAoGBANkmWIAsKkL1Bv3PiFA65IRQ
EOSc65rui70M5tvrDpka1jl6QgvGY/jI/6D6h8sZBxyYyncgWaCA4dVv9dmdZm8Z
JPXACUfHTJuk7ApPq2oYjyheyQkSLp8kYP47cidbNfWk3RkTRqwleh3ByG4e1Qxh
sfdf5owA1yuW5JSygppvAgMBAAGjIDAeMA4GA1UdIwQHMAWAA3p6ejAMBgNVHQ4E
BQQDenp6MA0GCSqGSIb3DQEBBQUAA4GBACMLNye3bEzTnHJAroAiV8Rw9rL6QG+x
wrFDBq173MXTAnKar/TujUxfmOzNZCxjPHh6oKRosOWZuI5v8/0wG9I6irYwLXOw
kXMvXT91/m5Vk7rLCqQ+zsFncxg12leHRgglWh1wsJOhPI/B0mYgCA04RNHsm+iC
/XjRBlAt1kMb
-----END CERTIFICATE-----

Here's the output of openssl x509 -in mycert.pem -text -noout on this cert:

Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number:
            54:2a:db:61:94:41:ba:d4:b5:91:ae:5f:c9:47:b6:88:ec:c5:02:6c
    Signature Algorithm: sha1WithRSAEncryption
        Issuer: O=phpseclib demo CA
        Validity
            Not Before: Dec 10 16:10:20 2017 GMT
            Not After : Dec 31 23:59:59 9999 GMT
        Subject: O=phpseclib demo cert
        Subject Public Key Info:
...
        X509v3 extensions:
            X509v3 Authority Key Identifier:
                keyid:7A:7A:7A

            X509v3 Subject Key Identifier:
                7A:7A:7A
    Signature Algorithm: sha1WithRSAEncryption
....

For brevity I've stripped out the "Subject Public Key Info" and "Signature Algorithm" sections from both.

Anyway, note how in the signed cert both the "X509v3 Subject Key Identifier" and the "X509v3 Authority Key Identifier" extensions are present. In the signing cert neither are present.

It seems to me that since the signing cert doesn't have a "X509v3 Subject Key Identifier" while the signed cert does have a "X509v3 Authority Key Identifier" that the cert ought not validate. And yet in OpenSSL it does:

openssl verify -verbose -CAfile signer.pem signed.pem

So who's correct? Is my interpretation correct or is OpenSSL's? Is there any RFC that discusses what the behavior ought to be in this scenario?


texts:
This question while asking for something different brings up an intriguing problem: If you can find $x$ such that $x\equiv R^x\pmod p$ then you can break DSA. Now I thought that one might be able to relate this to the discrete logarithm problem somehow, but I failed to find the relation and so I'm asking this (somewhat more general) question.

Now my question is:
Let $p$ be an arbitrary prime, does there exist an algorithm faster than $\mathcal O(p)$ which, given $p$ and an arbitrary $R\in\mathbb Z$, finds an $x\in\{y\in\mathbb Z\mid 0\leq y<p\}$ such that $x\equiv R^x\pmod p$ if such an $x$ exists or $\perp$ otherwise?


texts: Is one-time pad encryption vulnerable when near identical data is sent many times with different OTP?

texts:
Let's assume a text file that grows at its very end but is otherwise not edited. We now have 100 transmissions of this, but OTP-encrypted (different OTP each time, of course). The first 50% of the original file are identical.

Of course nothing can be said about the other 50%. But can parts of the first 50%, which stay perfectly identical, be attacked?

(Please be light on the lingo and math, I'm a noob.)

Different scenario, same question: The text is edited in various places, but only individual sentences. This shifts the bytes around, but apart from that, most of it stays perfectly identical.


texts: Issue implementing Pollard's Rho for discrete logarithms

texts:
I've been trying to implement Pollard's Rho recently. The original idea was to implement the code in several languages and put it up for everyone to see for educational purposes. I first took to Wikipedia and implemented the code from Pollard's rho algorithm for logarithms. I translated the code directly from C++ to Haskell and it generated the same output as C++ so I was happy. It agreed with the example in the Wikipedia page. However, when taking the output and solving $(B - b)\ \gamma \equiv (a - A)\pmod n$, I got results that were different than what the logarithm should be. If you would like to comment on this code, comment on the C++ code in the Wikipedia article please, I guess that's the most accessible version.

Unhappy with the Wikipedia article I searched further and found a gist with Python code that's based on Algorithm 3.60 in the Handbook of Applied Cryptography, linked in the gist. This version could calculate the logarithm for the example mentioned in the code (taken from the book). It yields different results to the code from the Wikipedia page. I have verified, and the Python code reads exactly like the algorithm is described in the book. However, if I feed it something like $n=6,\ Z=7,\ alpha=5,\ beta=4$ then obviously the $dlog$ of $4$ to the base of $5$ in $\mathbb{Z}_7^*$ should be $2$, because $5^2\pmod 7 \equiv 25\pmod 7 \equiv 4 \pmod 7$. But instead it breaks down with an exception, because it tries to get the inverse of $4\pmod 6$, and obviously there isn't one, because $gcd(4, 6) = 2 \neq 1$. It does that because in the last step of the algorithm, described on print page 106, it will arrive at $r = b_i - b_{2i} = 4$ and it has to compute $r^{-1}$. HAC is supposed to be a respectable book, but the code I have yields bad results, so am I doing something wrong? Is the book wrong?

I've spent a few days on this now. And yes, I've read through this stack exchange searching for Pollard's Rho. How do I fix this code? Why does the Python and C++ code break down? Is there a version of Pollard's Rho algorithm that generally just works other than for a few select cases? Is there a book that describes such an algorithm? Can someone point me to a working version?


texts:
I have a FPGA and am curious what cryptographic applications I can use with it.  I'm just a hobbyist / security researcher and not a professional cryptographer.

Since I'm creating my own curriculum, what cryptographic goals should I have with regards to the FPGA device?  (note I'm not looking for FPGA programming advice, that's a goal all in of itself)

I'm also interested in learning what won't work with a FPGA... in other words, what algorithms are or aren't suited for a FPGA?


texts: What does encryption with RSA public key provide?

texts:
I want to know if encryption with RSA public key provides confidentiality and integrity. I'm quite sure that it provides confidentiality but I have concerns about integrity.
If an attacker would scramble ciphertext what would be the result I get?
Do I need to put some kind of MAC at the end of messages before encryption?

If I have to be more specific about my problem, I want to use RSA for sending tiny requests to a server. I am thinking of encrypting requests with server's public key. Server will also know my public key and send back responses encrypted with my public key. I'm not sure if I'm using these correctly since I'm a beginner in these topics.

Any help would be appreciated.


texts: Security implications of the key padding in HMAC

texts:
I just learned HMAC in class.
Keys are zero-padded in HMAC hashing function.
10 and 1 will be both transformed into the same final key (e.g. 1000).
Isn't that a problem?


texts: Is RSA-OAEP secure against Shor's factoring algorithm

texts:
I've seen in this answer Can Shor's algorithm compromise RSA when both the public and private key are secret? that if textbook RSA is used (deterministic) the Shor's algorithm can reak it. However, if RSA is used with OAEP then Shor's algorithm cannot break it. The reason is that the known-plaintext pair doesn't include the randomness in the OAEP;
rfc8017 section-9.2

d.  Generate a random octet string seed of length hLen.

rfc8017 B.2.1.  MGF1

maskLen intended length in octets of the mask, at most 2^32 hLen

Then one needs $2^{31}$ try to break the RSA on average if they are able to produce enough Q-bits.

Is my understanding correct?

If so, then make the seed >128-bit and be safe from Shor. Then, why there are so much fear of Shor's algorithm for RSA?


texts: GMAC vs HMAC in message forgery and bandwidth

texts:
Saarinen in his work GCM, GHASH and Weak Keys says that:

  The GHASH algorithm belongs to a widely studied class of Wegman-Carter
  polynomial universal hashes. The security bounds known (this and this) for these algorithms indicate that a $n$-bit tag will give $2^{−n/2}$ security against forgery.

  It can be argued that universal hashes sacrifice some communication bandwidth for convenience as traditional hash-based MACs are designed to reach the information theoretic $2^{−n}$ bound against message forgery.

What is the convenience of universal hashes provides?
How much GHASH increase on the communication?.
Why one should not use an information theoretic bound HMAC instead should use a lesser one?
Since GHASH provides at most $2^{64}$ security against forgery in TLS 1.3, and that is standard that cannot be changed, are there any other suites that provide information theoretical security against forgery.

note: He also says that

  In this paper we give further evidence that this is not only the security lower bound but an upper bound as well. (for universal hashes )


texts: Cracking pdf file with arabic password using hashcat

texts:
I have been doing some test on password strength using arabic passwords and try to crack it using hashcat and when i used a non salted hash like a custom generated md5 hash and tried using --hex-charset parameter and it works like a charm but when i try it on pdf files it is not working i even decreased the password to 1 character

in case you are wondering:

i followed this blog http://blog.bitcrack.net/2013/09/cracking-hashes-with-other-language.html but works only for non salted hashes.
i used pdf2jhon.py to extract the hashes.
yes using the above steps it can also work for english.
--hex-salt is not supported on 10500(pdf format)

My assumptions are:

1.maybe the pseudo random salt generator takes chars from the password itself

2.the password hashing algorithm stores the password in unknown charset format when the password is from non-English chars

So my question is:

1.is there another workaround on this(is it possible)?

2.if my 2nd guess is correct please tell me what unicode?

UPDATE
after researching i found the problem is the tool used to encrypt the file uses non ASCI characters when using non ASCI characters in my case arabic i am trying to use utf-8 format like D985 can someone tell me which unicode microsoft office and adobe acrobat use when using non ASCI characters.


texts: How to attack a fixed LCG with partial output?

texts:
To show some colleague programmers exactly how broken C's rand() is (at least on Windows) I decided to break it. So everyone knows the exact parameters, MSVC's implementation is as follows:

uint32_t state;

int rand() {
    state = state * 214013 + 2531011;
    return (state >> 16) & 0x7fff;
}

Because the top bit never affects anything but the next top bit in the next state and is never returned you could see this as the LCG $X_{n+1} \equiv (214013X_n + 2531011) \mod 2^{31}$ where at each iteration we only get to see the top 15 bits.

The problem is, I have not found any references that attack fixed LCG's with partial output.

Of course it requires only 2-3 calls of the rand() function to enable a bruteforce attack with at most $2^{16}$ operations on the secret part of the state, but that's hardly a break. Something similar would not be feasible with larger constants and a larger modulus.

So far I've been unable to find a break that shows this generator to be severely broken. I'm interested in results on similar LCG's that can be transformed to an attack on this one.

P.S.: If an attack exists that could be done on a graphical calculator without any programming, it increases how convincingly I can show the generator to be broken. But this is just bonus points.


texts: Need tips on how to break Fiat-Shamir sigma-protocol (programming challenge)

texts:
I'm completely stuck on an university programming challenge and I need some tips to get me out of the valley I'm in, you don't need to give the full answer if you do not wish to.

What we have:
Fiat Shamir sigma protocol, described as follows:

A trusted center chooses $n=pq$, and publishes $n$ but keeps $p$ and $q$ secret.
Each prover $A$ chooses a secret $s$ with $\gcd(s,n)=1$, and publishes $v=s^2 \mod n$.
$A$ proves knowledge of $s$ to $B$ by repeating:

(a) $A$ chooses random $r$ and sends $r^2 \mod n$ to $B$.
(b) $B$ chooses random $e$ in $\{0,1\}$, and sends it to $A$.
(c) $A$ responds with $a=r\cdot s^e \mod n$.
(d) $B$ checks if $a^2 = v^e r^2 \mod n$.

We have knowledge of all the information sent in the messages between the parties during two runs of the protocol, notable is that these messages are using the same nonce, one message has e = 1 and one message has $e = 0$

So basically we have:

$r_2 \mod n$ (note also that $n$ is longer than $r$),
$e
,
a$

and the public information: $n, v$

What we want:
$s$ (which is $v=s^2 \mod n$ as seen above)

What I've tried:

The only solution I can come up with that I believe in is the following

consider that we have ( $a = r\cdot s^e \mod n$) for two runs
consider that one run has an $e$ of $1$, one has an $e$ of $0$
Logically then the run with $e = 0$ would send ( $a = r \mod n \rightarrow r $)
$e = 1$ would send ( $a = r \cdot s^e \mod n$)
To my knowledge the nonce is $r$, and the first message with $e = 0$ gives away $r$
So just take $r^{-1} * a$, since $a = rs$ when $e$ is set to $1$
That should leave us with $s$

Problem:
When I try to use the $s$ to decode the message with a given function it just returns gibberish, the value is not decoded with the $s$ that I have recovered, so clearly I am doing something wrong, but I have no clue of what.

Any tips would be highly appreciated


texts:
I need help during implementation of C# interface (.NET framework) for encryption of messages which are sent to/from HBCI (Homebanking Computer Interface) server according to RDH-10 standard.

Predispositions for the encryption process are as follows:

Signature algorithm: RSA
Operation mode with signature: RSASSA-PSS [PKCS1], owner signing
HASH algorithm: SHA-256
Encryption algorithm: 2-Key-Triple-DES, CBC (0-Padding)

The mask generation function MGF1 is used as part of the padding process RSASSA-PSS. On the signing key is a double Hashing carried out. The length of the hash value is to be used as the salt length.

As a final result I need to be able to encrypt a message assuming that I have signing key and encryption key from the server. Those are 2 keys which I received:

Encryption Key:
Modulus (248 bytes)
(HEX) d3 60 fd 45 4d 23 68 d5 ca 2a 1c f7 42 bf f1 59 ae 69 1a c6 b2 30 6f f8 0b 7e 18 73 25 e5 13 fe 9a 78 6f 86 ad c8 b2 3f 8d 5b b2 83 bd 1b 9b ec e2 ab 60 26 2f 35 78 26 32 ea 88 02 e9 79 0d 51 0a 64 e9 37 68 21 13 8d 38 d9 95 85 fe 80 41 04 00 0f 7d 7c 20 2c 4c 04 c3 da d4 51 62 aa 59 d7 5e a6 44 1f 8a fb ab 2a 31 96 7e 77 8d c3 e5 f5 f3 bb 6d ab 8c f7 a9 5a 5e da 71 26 77 db ff 12 af 66 92 87 70 e1 92 28 15 83 9d b4 8d 42 48 cb 9b 71 9e d8 21 91 34 e0 d5 56 00 f7 3d 33 3c e5 cc f5 a4 ba cf c9 47 3d f3 25 8a 0c 82 0d 88 87 f4 08 d2 5c 0a 6a d9 92 61 47 5d 67 6c 44 24 a7 3d 07 4f 10 bf bd 5e 78 1b 38 d2 e0 af d7 74 1f a1 bc d7 35 db 26 f8 7a b6 b1 a1 1e c1 b6 6a 17 e2 3f b9 5f 8c b0 e1 e1 98 73 32 af bd 14 b2 ae ec 42 3b 81 f2 b1 98 33 (HEX END)

Exponent (3 bytes):
(HEX) 01 00 01 (HEX END)

Signing Key:
Modulus (248 bytes)
(HEX) ce 6d f9 de b5 74 5b e8 d5 00 94 c1 0f 88 86 b5 f0 0f 3e 0c 0c fe 6e e9 6f c2 0f e6 30 74 fa d3 31 84 91 e0 29 42 fc e3 92 00 49 f7 da e2 db 1c fd 74 e9 a7 f1 f9 6a e6 f5 60 49 31 8c 65 71 49 6b c4 2e 3d fe 8c 1a 4b 53 2f 47 d2 51 ce e4 22 2c 1e 3a 6a 98 58 e0 50 4e cb e2 18 c6 f9 96 06 ce 9d 37 71 c3 0c 57 7f f6 06 24 16 b5 36 82 ef 1b 17 04 05 72 9a 33 67 83 5f 88 58 dc 18 ab 98 fe 99 27 3f 51 a1 c7 76 aa 81 05 db 49 5d 4c 65 d3 f4 a6 94 69 a8 32 c7 3d e8 f3 a2 93 40 52 eb 2a 90 ba 3e 2b 32 53 6f 58 50 83 97 23 2a de 90 c1 79 e7 14 fd 9c cb 3c fc 66 e8 e2 5a 6b 6d 3c a4 f1 23 78 85 e5 05 c5 cf c7 ab fe 5b 75 16 f7 78 1a 5d 5b ea e9 d6 92 36 81 a2 b6 a9 d6 aa e9 1c 45 59 65 ca 02 0c 6d 42 5b 00 e8 cf a6 7c 7a ce 00 6e 7c 71 1b 5b bd (HEX END)

Exponent (3 bytes):
(HEX) 01 00 01 (HEX END)

There is also a electronic signature:
(HEX) 31 06 ec f2 08 b0 8f 64 62 a9 db 20 d4 62 39 96 65 81 e5 61 f9 03 3b 50 18 68 3a e5 93 df a9 d6 29 22 ca f0 f7 8a 95 f1 f6 aa 5e a3 1f b9 b2 70 33 42 f2 cc b5 80 ce 7f e8 58 aa d8 20 2c 03 83 ba b2 6d 45 b7 bf 5f 1d 71 5c 81 15 6d 7f c2 04 b2 56 70 c7 a1 79 47 d0 a5 ca 5e 46 36 02 0e 19 26 ec f5 30 80 cc 90 49 22 14 a7 96 51 74 db f8 72 42 ca 73 30 77 11 d3 a1 61 05 39 85 96 2d f4 50 77 3a 80 1d da 39 e1 97 a2 e7 ba ed f5 8c 70 6a f3 e8 3c 42 8f 64 79 61 60 cb ae 25 c8 88 a8 87 93 1c e8 64 e0 f7 6b 7c 30 48 73 ca b7 e1 57 e8 f2 17 f9 83 d7 21 73 1e 34 cf 67 04 92 ae 7b ee b6 6f 60 be 74 e8 da e9 01 86 f3 cd ea 01 7f c0 fa 44 e7 82 98 db bb 93 7e 7d 10 4f 9c 41 4c 8f af 0f 28 b9 f3 f0 88 05 37 3a 3a c6 83 38 bd ad dc 1e d2 df ca 18 7e (HEX END)

I really hope you can help me with some guide, some code snippets etc.

Thanks!


texts: What Diffie-Hellman parameters should I use?

texts:
After reading this article, I started wondering how should I approach the problem of choosing p and g params in 1024-bit Diffie-Hellman key exchange.

In my project, I am going to establish keys between many users. Should I create different p and g for every one or e.g. every 100? Is there any tool that would generate me random and good p and g params (g to be generator of p group) which are considered cryptographically safe? Or is switching to 2048-bit the best solution?


texts: Encrypt data. Create 5 keys. Just 3 keys are needed for decryption

texts:
I would like to encrypt some data and create 5 keys. These keys are stored in different places. If I want to decrypt the data I just need 3 of these 5 keys.

Is there a way to do this?


texts: Which elliptic curves are quantum resistant?

texts: If I want to learn about quantum resistant crytography what are the best resources? Which type of elliptic curves should I be studying?


texts: What is the best way to sign a message using RSA?

texts:
I was preparing for competitive exam, and I came across this question. I had a lot of discussion with my friends before I resorted to posting it here and I wanted myself to be clear on this.

Let $M$ be a confidential email that Alice wants to send to Bob,  $K_B$ be Bob’s encryption public key, and  $K_A^{-1}$ be Alice’s private key for signing. Which of the following options would be the best choice for protecting confidential emails?

(A) Send $E_{K_{B}}(M),Sign_{K_A^{-1}}(K_B)$

(B) Send $E_{K_B}(M),Sign_{K_{A}^{-1}}(M)$

(C) Send $E_{K_B}(M),Sign_{K_{A}^{-1}}(E_{K_B}(M))$

(D) Send $E_{K_B}(M),Sign_{K_{A}^{-1}}(K_{A}^{+1}(M))$

I marked (B), but correct answer is given to be (C).

I understand the first part, that we are encrypting the message with Bob’s public key, but my understanding says, that we sign the message using Alice’s private key and send it to Bob along with the encrypted message.

But seems like option (C) says that along encrypted message, Alice should sign the encrypted message and then should send this signature along with the encrypted message to Bob.

My query is as per option (C), Why are we signing the whole encrypted message instead of the original message as shown in (B).


texts: What's the difference between perfect security and unconditional security?

texts:
This paper refers to two distinct security models: perfect security and unconditional security. Until now, I knew of them as the same thing and equivalent to information-theoretic security.

From the paper, it's obvious that perfect security is the same as information-theoretic security. In this case, what exactly is unconditional security?


texts: Use of shared secret "other" than key creation

texts:
I have read and (believe) I understand the basics of key exchange / creation over a public channel of communication from this diagram Diffie–Hellman key exchange.

Now, a fair bit of the online documentation states what has been produced by this process is a "shared secret" not a "shared secret key", nor any references to keys. The documentation does indicate what has been produced can be used as a (shared private?) key. But is the "shared secret" ever used for anything other than a key - I can't think what, but that's why I am asking the question. It was just the term "shared secret" without reference to "key" that prompts this question.

Edit:

This has been answered (but I can't find a way to indicate that on this post), so see comments below and : How to encrypt a symmetric key with a shared secret?


texts:
RFC 2104 says:

  Applications of HMAC can choose to truncate the output
  of HMAC by outputting the t leftmost bits of the HMAC
  computation for some parameter t [...]. We recommend
  that the output length t be not less than half the
  length of the hash output (to match the birthday
  attack bound) and not less than 80 bits (a suitable
  lower bound on the number of bits that need to be
  predicted by an attacker).

Obviously, different lengths of HMAC outputs provide different levels of security. What's not obvious to me, is: If one needs the security provided by a 128-bit MAC, why is HMAC-SHA-256 suitable to generate such (half the length of the hash = 128 bits) but HMAC-SHA-512 is not (half the length of the hash = 256 bits)?


texts:
Suppose one had a complete list of primes up to $2^{n+1}-1$. Then wouldn't one be able to crack an $n$-bit RSA public key in time $O(\pi(2^{n+1}-1))$, making RSA insecure?

Thanks,

René


texts: Find Points of order 2 on elliptic curve

texts:
Suppose there is an elliptic curve

$E:y^2=x^3+(p-1)\cdot x\bmod{p}$

with $p>3$.

The question is: What are the points that have an order of 2?


texts:
In 1993, Anderson [1] proposed a backdoor to the RSA key generation algorithm. This backdoor requires that a backdoor key (prime) $A$ be implanted within the key generation portion of the RSA algorithm.
Instead of the usual way, primes $P$ and $Q$ are generated using the following algorithm:
First define a backdoor prime $A$ and two smaller random primes $P'$ and $Q'$.
Let $k=1$
$ \text{If} \ \ isprime(A\cdot k + P'):\\
\quad P = A\cdot k + P' \\
\text{else}: k = k+1$
The analog is performed for $Q$ using $Q'$.
This algorithm was also described here Is there any more information on this RSA backdoor?
This backdoor allows to calculate $N′= N \mod A$ and then factor $N′$ into $P′$ and $Q′$. Still $N'$ needs to be factored, but this is now a much easier problem as $N'$ is only about a fourth in size of $N$.
Please note that in my algorithm above I used $k=1$, the original implementation by Anderson suggests starting value $k=P'$ and iteratively increasing $k$ by one until $P$ is prime. In my algorithm I start with $k=1$.
My questions are:

does starting the iteration from $k=1$ instead of $k=P'$ make a difference?
in the way $N'$ is generated, what is the best way to factor $N'$ given the information how it is generated? Is there a certain factoring algorithm that makes factoring $N'$ very easy?

[1] Ross Anderson. Practical RSA Trapdoor. Electronic Letters. 29(11): 995,
1993.


texts: Achieving 256-bit encryption strength with PBKDF2 - HMAC-SHA1

texts:
I am interested in the theoretical consideration of the bit strength of an encryption key and its precursor.

Assume a given environment as follows:
a. My encryption algorithm is AES-256
b. My key derivation function is PBKDF2 with HMAC-SHA1 with
   b1. Salt strength of 128 bit (32 chars of a truely random hex string)
   b2. Iteration count is 4096

My objective is to achieve 256 bit "encryption strength" based on the above environment

Evidently, I can not achieve a "true 256-bit total strength" with the environment as stated above, since the randomness provided by the SHA1 in the PBKDF2 standard is at most 160 bit.
From RSA Document "PKCS #5 v2.0: Password-Based Cryptography Standard", March 25, 1999:
"The length of the derived key is essentially unbounded. (However, the maximum effective search space for the derived key may be limited by the structure of the underlying pseudorandom function"
and

"....Thus, even if a long derived key consisting of several pseudorandom function outputs is produced from a key, the effective search space for the derived key will be at most 160 bits. Although the specific limitation for other key sizes depends on details of the HMAC construction, one should assume, to be conservative, that the effective search space is limited to 160 bits for other key sizes as well."

My questions is:
Since the most I can expect is "160-bit encryption strength" from my existing environment, if I feed the result of the PBKDF2 output to a Skein 512-512 hash function, and use the left-most 61 hex (=244 bit) characters of its output as an encryption key, will I then have my sought-after 256-bit total encryption strength (I have added the 12 bit extra "strength", due to iteration count, to my calculations)?


texts:
Is there any known way to construct a length-preserving all-or-nothing transform?  In other words, a secure all-or-nothing transform where the length of the output is the same as the length of the input.

My thanks to @Ricky Demer for suggesting this question.


texts: Exploit RSA , given some information about n

texts:
Every week Bob updates his public RSA modulus $n=p*q$ and encryption
  exponent $e$ by picking a new pair of primes $p$ and $q$ and a new exponent
  $e$. After several weeks, bob becomes lazy and decides to keep the prime
  $p$ fixed and only updates the other prime $q$ every week. Eve hears about
  this. How can she exploit this information to decrypt messages sent to
  Bob using his public key ?

I don't know how to solve it, any help or hint would be much appreciated.
I understand we need to retrieve $p$ and then we can get any $q_i$, and from there decipher the messages, but how can we do that ? okay so $n_1 = pq_1, n_2 = pq_2 , n_3 =pq_3$ , so on ... How do we get $p$


texts: Is a zk-SNARK the hash of a Linear Interactive Proof?

texts:
zk-SNARK researcher Eran Tromer came up with the following workflow when describing how these proofs are created:

What I am struggling to understand is how a LIP becomes a zk-SNARK. Is the SNARK a hash of the LIP?

I would appreciate any help, or recommendations for reading materials.


texts: Zencash uses your passphrase to identify AND unlock a wallet - how is this secure?

texts:
When looking into Zencash I stumbled into myzenwallet.io (by the Zencash creators), which gives you the option to enter a passphrase to generate a wallet (seems normal), but then after creating your wallet you can come back later and open your wallet by simply re-entering your passphrase again... this was unexpected and had me not only wondering about how it worked, but also wondering whether whatever means were used to achieve this would remain secure in the future.

Given that I don't need to identify the resource I'm unlocking, but rather just hand over the passphrase, I'm left to assume that their system generates a token by hashing my passphrase a number of times to generate my "master address" or "account ID" (I just made those terms up, because Zencash gives you many addresses, so I also assume you have some sort of master address / account ID), and then also using that same passphrase to lock / authenticate (not to encrypt though, right?) the wallet.


texts: Key space vs Cardinality of 1024-bit RSA

texts:
I have been trying to figure out the encryption key space, and cardinality of 1024-bit RSA. From my understanding, the key generated from 1024-bit will be primes greater than $2^{1023}$ but less than $2^{1024}$. So, there are approximately $8\times10^{307}$ types of keys that can be used.

Is this the key space or the cardinality, and how do you distinguish the two from RSA ?


texts: Encryption algorithm multiple threads/cores for higher throughput

texts:
There are situations where a single connection (or file) may require additional throughput available. While network bandwidth and CPU cores are available, they cannot be utilised. (Aside from means that are external to the algorithm as is)
Some examples:

VPN - when encryption is done only on the tunnel connection that internally encapsulates packets of multiple flows.

Typically, it is thought that an encryption algorithm itself is a sequential process, that relies on the previous block or bit(s) in order to accomplish effective cipher strength. This means the algorithms cannot be multi-threaded.
Is this true of all encryption? Does this apply equally to modern common algorithms (block and stream)?
Is there a way to purpose-make an encryption algorithm that works on multiple threads (cores)? Are there any existing algorithms (perhaps not common or academic only) that would work across multiples cores?
Usually, this isn't a problem, because machines may make use of multiple connections (HTTPS), but it means a single connection is limited by the cipher transform speed of a single CPU core. Also, when multiplexing is used (like VPN), this might be a particularly limiting issue.


texts: As stated here Ed448 is different from Ed25519 because of "spinal-tap grade" security. What does this mean?


texts: Is it the same as the bits of the key (So a 2048 bit system will yield a 2048 bit signature)? At most as the key? Or something else entirely?


texts:
In learning how DH works for cryptography applications, I'm coming across some confusing language. For starters, most of the time DH is discussed in the context of "generating" their shared secret. However, I'm also seeing that it can be used for encryption purposes as well (such as encrypting the shared secret using an ephemeral key).

As a concrete example, I'm trying to encrypt with the following formula:

y = mgabmod n

However, I'm having trouble finding how to decrypt based on that formula. What is the use case for that formula, and what is the decryption process?


texts: DH Elliptic Curves: Why choose a fixed base point?

texts:
I am having a first look at the TLS key exchange using Diffie Hellman and try to understand the Elliptic Curve variant of it.
So if a client and a server agree on using ECDH for key exchange and they use the secp256r1 curve, it seems like the base point G is given and they take it from the standard (04 6B17D1F2 E12C4247 F8BCE6E5 63A440F2 77037D81 2DEB33A0F4A13945 D898C296 4FE342E2 FE1A7F9B 8EE7EB4A 7C0F9E16 2BCE33576B315ECE CBB64068 37BF51F5)
From my understanding, i could use an arbitrary base point G and obtain a group which i can use for my key-exchange. Whats the advantage of using a fixed one?
Knowing the base point, wouldnt it be possible to create some kind of rainbow-table and thus crack some connections?
To me it seems more intuite that picking a new base point G every time would increase security.
But as far as i understand it, it's not whats done in TLS.
Can anyone tell why we pick a fixed base point instead of generating a new one for each key-exchange?


texts: Rivest's ring signatures with hashes instead of symmetric encryption

texts:
While studying ring signatures, I obviously stumbled on the Wikipedia article about ring signatures. It includes a piece of Python code to demonstrate "How to leak a secret" ring signatures.

Remarkably, they do not use a symmetric encryption function ($E_k$, as in "How to leak a secret"), but a hash function ($\mathcal{H}$). Indeed, the encryption function does not need to be invertible, if we close the ring of the signature at the very last (take $v^\prime$ random, $m$ is the hashed plaintext):

\begin{align*}
\mathcal{H'}(x) &= \mathcal{H}(x\mathbin\Vert m)\\
v&=\mathcal{H'}(y_{r} \oplus \mathcal{H'}(y_{r-1} \oplus \mathcal{H'}(\ldots\oplus \mathcal{H'}(v'))))\quad r-s\enspace\text{times}\\
h&=\mathcal{H'}(y_{s-1} \oplus \mathcal{H'}(y_{s-2} \oplus \mathcal{H'}(\ldots\oplus \mathcal{H'}(y_1 \oplus v))))
\end{align*}

now notice that
$$
v'=y_s \oplus h \quad\Leftrightarrow\quad y_s=v'\oplus h\\
x_s=g_s^{-1}(y_s)
$$

which "closes" the ring.

What are the security implications here? I can't seem to find literature describing this substitution.


texts: What implementation properties of a hash function prevent safe truncation?

texts:
Truncating a hash function's output should, in theory, not increase the likelihood of a collision more than you would expect based on the truncated output size. This makes sense when thinking about the the ideal hash function, a random function.

Since real-world hashes are not random functions, what properties of algorithms like sha2 make us comfortable with truncating, and what (popular) hashes exist out there that are known to have issues?


texts:
The Paillier CryptoSystem has a public key that $(g,n)$ and the private key which can be exclusive to $\lambda$, where the decryption scheme is:

$m = L(c^\lambda \bmod n^2)/L(g^\lambda \bmod n^2) \bmod n$

Since $1/L(g^\lambda \bmod n^2)$ is fixed and always needed for decryption, it is usually computed once and denoted as $\mu$.

What information does $\mu$ leaks about $\lambda$? Because at the end of the day, even if I have $\mu$, I cannot decrypt. i.e. Can I get $\lambda$ from $\mu$?

A Side Note on the way $\mu$ is constructed, that I think proves the correctness of the assumption:

\begin{align}
    g &= (1+n)^\alpha \cdot \mathcal{B}^n \pmod{n^2} & & \text{$g$ in the $n^{\text{th}}$ root form} \\
    g^\lambda &= (1+n)^{\alpha\lambda} \cdot \mathcal{B}^{n\lambda} \pmod{n^2} & &\text{so base on carmichael's theorem} \\
    g^\lambda &= (1+n)^{\alpha\lambda} \pmod{n^2} & & \text{again, based on $n^{\text{th}}$ root rule}\\
    g^\lambda &= 1+n\alpha\lambda \pmod{n^2}&  & \\
    L(g^\lambda) &= \alpha\lambda \pmod{n^2}&  &\\
\mu &= 1/\alpha\lambda \pmod{n^2} &
  \end{align}
So, since it is impossible to get $\alpha$ given $g$, the main complexity of the encryption scheme itself, and the last equation is a function of two variable, and there is no way to find either variable.


texts: Are there any key exchange schemes that only require entropy on one side?

texts: Are there any cryptographically secure (in terms of confidentiality) key exchange schemes which are usable if one partner in the connection is entirely deterministic and has absolutely no entropy? I know the basics of the operation of several asymmetric ciphers but am not a cryptographer. I wonder this because it seems like it would be easy to provide initial entropy to embedded devices through an encrypted connection without running into the chicken and egg problem of needing entropy to securely connect to a service to retrieve entropy. If this is possible, is authentication also possible?


texts:
Is it safe to XOR parameters like domain, length of the message or block counter into sponge's capacity or that gives attacker control over capacity?

For example NORX XORs domain into capacity.

Does this break sponge security proofs?

What about adding bit into capacity to denote that there was no padding since message was multiple of rate and therefore reducing number of permutation function executions?

PRIMATEs use padding spilling which is similar to no-padding bit. Their paper says:

  Note that the spilling of the padding in case |M[w]| = r causes
  security to degrade by half a bit: intuitively, APE is left with a
  capacity of c' = c - 1.

However, it looks like this doesn't apply to HANUMAN and GIBBON which also use the same padding spilling.


texts:
I just read through this article which demonstrates practical (and seemingly trivial) collisions in PBKDF2-HMAC-SHA1, and provides a few examples of collisions.

Am I missing something here? Is PBKDF2-HMAC-SHA1 really broken this badly and trivially? Or am I missing some wider context?


texts: Do other one-time signature schemes exist?

texts:
I'm curious to know if there are any one-time signature schemes other than Lamport's or its variants (Merkle trees are one such variant). The first I've discovered is called "Bins and Balls" which doesn't use a trapdoor function.

Any others? Are they smaller than Lamport signatures? I'd like descriptions, too (also of BiBa).


texts: advantages of hashing over elliptic curve signatures for a proof of work protocol

texts:
I'm trying to create a proof-of-work protocol for a proof-of-concept software, and it's basically something like this:

privkey = that user's private key
pubkey = that user's private key

both are ECC

message = "some message"
difficulty = advertised difficulty

log2 (sign(privkey, hash(pubkey+"|"+message+"|"+difficulty+"|"+hard_worked_nonce))) < difficulty

This means that the signature must begin with a specific number of zeroes, as advertised in the message; else the message is discarded as spam.

The user must compute a had_worked_nonce which will render the condition above as true.

Is it any reason why i couldn't skip hashing and only do this? I plan on using ed25519.

log2 (sign(privkey, pubkey+"|"+message+"|"+difficulty+"|"+hard_worked_nonce)) <= difficulty


texts: Zk-SNARK against Sigma Protocols and for Secure Function Evaluation

texts:
I have a couple of questions on ZK-SNARK:

Based on what I understand, a ZK-SNARK is an "Argument of knowledge". That means that it should be equivalent to Sigma Protocols like Fiat-Shamir and Pederson committments, RSA Accumulators, and even attribute-based encryption, correct?
I've read in a few places, like Prof. Bill Buchanan's intro, that a ZK-SNARK could be used to "delegate" a function in order to have a 3rd-party (call her Alice) to calculate a function without her knowing what she is calculating. For example, we can calculate the function aX + bY, if X and Y are private to Alice. We can do this by using homomorphic encryption around Enc(aX + bY), to which we can calculate Enc(aX) * Enc(aY), given that a and b are public. In this case, we will know the result of aX + bY without knowing X and Y. Is that a correct representation of Zk-snark (AKA: Secure Function Evaluation)?

Did I mix up too many categories together?

Many thanks in advance


texts: What does that mean, that A5/1 is clocked? What happens if the clocking bit agrees with the majority bit?


texts: Security assessment between $g^{a_ix_i+r_i}$ and $g^{x_i+r_i}$

texts:
Imagine a tagging system whose security requirements imply to learn nothing from the tag about the encoded value.

We consider a plaintext space $X \in \mathbb{Z}_p$ and a group $\mathbb{G}$ where the DLP is computationally hard.

The sender sends $\sf{tag_1}=g^x_i$ where $g$ is a generator of $\mathbb{G}$. This is not really secure in the sense that we provide the attacker an oracle to verify its guess on values in $X$.

We change the tag to be of the form $\sf{tag_2}=g^{x_i+r_i}$ where $r_i$ is a random value from $\mathbb{Z}_p$

We consider another tagging scheme where $\sf{tag_3}=g^{a_ix_i+r_i}$ where $a_i, r_i$ are random values from $\mathbb{Z}_p$

Is $\sf{tag_3}$ more secure than $\sf{tag_2}$? Is there an attack in $\sf{tag_2}$ which is mitigated with $\sf{tag_3}$?


texts: Can I replace DH by a post-quantum key exchange in IBAKE for post-quantum identity-based authenticated key exchange?

texts:
IETF RFC 6539 IBAKE - Identity Based Authenticated Key Exchange describes a Hybrid key exchange using both Identity based cryptography and a standard ephemeral elliptic curve Diffie-Hellman key exchange.

Since that protocol already is a hybrid could one replace the elliptic curve Diffie-Hellman exchange from IBAKE with something like SIKE or some other PQC scheme and use that for an effective PQ Hybrid?

It seems like a PQ exchange inside of IBAKE would give users long term protection against quantum computers.


texts:
In Section 8 of this, Lindell presents a construction of an oblivious transfer protocol which is secure in the malicious model under the following variant of the DDH assumption (page 53):

  [F]or every probabilistic-polynomial time non-uniform distinguisher $D$ there exists a negligible function $\mu$ such that
  $$|\mathrm{Pr}[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^r) = 1] - \mathrm{Pr}[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^{r+1}) = 1]| \le \mu(n)$$
  where $\mathbb{G}$ is a group of [prime] order $q$ with generators $g_0$, $g_1$.

It is then stated that this assumption "follows easily from the standard DDH assumption" using its random self-reducibility property (as described for example by Naor and Reingold).

As I understand it, random self-reducibility means that from any fixed instance we can generate a random one, which can then be solved by an assumed algorithm solving a random instance. Thus no particular instance can be harder than the average case, and so in particular the worst case is exactly as hard as the average case.

However, this does not seem to preclude a particular case from being easier than the average case, and in particular the case $(g^a,g^b,g^{a(b+1)})$, so I fail to see how the hardness of the average case (which is the "standard DDH assumption") implies the hardness of this particular case.


texts: How does the receiver compute the private key when using RSA?

texts:
I understand the public key and the private key are generated at the same time. The payload is encrypted with the public key. Sender Alice sends public key $[n,e]$ and cipher text $C$ to Bob.

Now is Bob recomputing the private key $d$?

If Bob is computing the private key $d$, can a "Man in the Middle" who gets the public key and cipher text also compute the same?

Or is there a scenario in which both Alice and Bob know the value of $p$ and $q$?

I am confused. Please help me understand this in a scenario assuming Alice and Bob are located in two different geographical locations.


texts: Relationship between the use of a mask and entropy

texts:
This is part of an assignment and I'm not sure what conclusion I'm supposed to draw from the result.

We were supposed to generate two 1024 bytes words, one using an algorithm that randomly generate 0 and 1 (50%/50%) and one using an algorithm with a "secret" probability distribution. I'll call them word 1 and word 2 from now.

We were supposed to calculate the empirical entropy of each word bit per bit first, and then byte per byte.

I got the following results :

word 1 (bit per bit): 1.00

word 1 (byte per byte): 7.79

word 2 (bit per bit): 0.95

word 2 (byte per byte): 0.81

We where then supposed to generate a random 1024 bytes mask and apply it on each word, giving us word 1m and word 2m. The results are this time:

word 1m (bit per bit): 1.00

word 1m (byte per byte): 7.81

word 2m (bit per bit): 1.00

word 2m (byte per byte): 7.81

I'm not sure what those results mean! Of course I noticed the fact that the byte per byte empirical entropy of word 2 is low, which probably means that some specific bytes are appearing more often than other, but I don't know what happen for word 2m

Not sure I made myself very clear, don't hesitate to ask for clarifications. Thanks !


texts: Estimate Security level of the Rabin Signature

texts:
I'm trying to figure out how long the modulus $n$ has to be in the Rabin Signature scheme, to provide 128 bit security.

We assume that the used hash function is "secure enough". Then the naive approach would be the following:

Since forging a signature is prooven to be as hard as factorization of $n$, the security level of the signature scheme is approx. equal to the bit length of $n$. Therefore for 128 bit security, $n$ should be at least a number,such that the fastest factoring algorithms take 2^180 tries. But how long is such a number?

Of course I know, that its said that RSA keys should  be around 3072bit to achieve 128bit sec. On the other hand RSA has no tight reduction to number factorization in contrast to Rabin.

Can someone therefore explain how to estimate Rabin modulus size?


texts: Why are the fully homomorphic encryption algorithms the commitment?

texts: Is there some references about the commitment scheme based on FHE ? Why could the BFV, CKKS, BGV algorithm be convert to commitment? How ?


texts: How to convert from small field to large field

texts:
If I have number $2$, which is additively shared into $3+4 \bmod 5$.
Now I need to change the filed to a large one, like $500$.
How to convert the shares, so that I can have a new number or shares $a+b \bmod 500 = 3+4 \bmod 5$.


texts: Is the half-homomorphic property of RSA a problem for blind RSA signatures?

texts:
For blind RSA signatures, is it problematic that RSA is half-homomorph?

Take a scenario where blind RSA signatures are used for something like a voting procedure or this proposal: Lots of people, potentially malicious, are given the ability to sign a limited amount of messages without revealing the content of the messages to the signing party.

The attack scenario I have in mind is as follows: The attacker lets the party with the private key blind-sign the primes in a factor base, then tries to create to-be-signed data that is smooth over the factor base, letting him make his own signatures by multiplying together the signatures he already knows.

Is that not a problem because so few numbers are smooth over a relatively small factor base?


texts: Is perfect-forward secrecy achieved with RSA?

texts:
I am new to cryptography and am going through the book Understanding Cryptography by Paar and Pelzl.

From what I understand Symmetric key distribution systems like Kerberos do not provide PFS because an attacker will be able to decrypt every session key ever encrypted with a compromised KEK.

In the book, on page 342, they say that Asymmetric ciphers like Diffie-Hellman or RSA, when used for key distribution, will provide FPS. I understand that Diffie-Hellman will provide PFS because each session key will have nothing to do with any other session key. However I've been stumped for a few days now trying to figure out how RSA will provide PFS. Am I missing something or just misunderstanding what they wrote?


texts: Does data authenticity always, implicitly, provide data integrity?

texts: Does a scheme which provides data authenticity (e.g. HMAC or RSA signature) always implicitly provide integrity? It seems, to me at least, that it must by necessity. However, I have seen cryptographers reference MAC, MIC, and MAIC as separate terms. In my experience, that usually means that there's a subtle difference that's important to pay attention to. However, if MAC and MAIC are identical, what's the reason for the distinction?


texts: Is it possible to distinguish ECC private key from the random values

texts:
I have a list of the random values (each 65 bytes long). One of the items is a private key which is used to sign the data:

Private key = KeyFactory.getInstance("EC").generatePrivate(
  new ECPrivateKeySpec(new BigInteger(<ONE OF THE ITEM FROM THE LIST>), ECNamedCurveTable.getParameterSpec("SECP521R1"))
);

Signature sig = Signature.getInstance("SHA256withECDSA");
sig.initSign(key);
sig.update(<data to sign>)
sig.sign();

I have no access to the correspond public key nor result of the sign().

Is there any way to find of which item on the list is a valid private key? I know that only one value is a private key.

Is a ECC private key random value? Or maybe it has a "structure" which can be used to distinguish it from other random values?


texts: Packing technique for large data storage

texts: Packing multiple plaintext messages into a single ciphertext block is known to increase the effeciency of homomorphic encryption. Can someone let me know if this technique can support large data ? For example, there is packing technique 1 that transform a binary vector to a polynomial of ring. However, the packing technique does not specifies what type of storage technique or file will be used to store the packed data. How we can know if a packing technique can support large message encoding and how we can ensure that the result can be stored correctly ? is there is a relation between the packing technique and the storage type of message or data ?


texts: Simulation based proofs, what am I missing?

texts:
In the example given by in the top answer of Simulation based proofs: Simple examples claims that this is insecure the semi-honest, and I need assistance in where I am failing to reason why that this is true.

By definition (at least put simply to my understanding), a protocol is secure under this simulation based definition if the output views of the simulator and the adversary are computationally indistinguishable.

In the case where $x_2$ is 0, the output of the computation is always 0. And in this case, the simulator has to guess the value of $x_1$, namely it can take either value of 0 or 1. In the case that the simulator guesses $x_1$ correctly, it's obvious that these views are identical. However, what I fail to understand is in the case the simulator guesses $x_1$ wrong, how are these views distinguishable? As far as I can see, no distinguisher should be able to tell if the view of $(1,0,0)$ with the message $1$ from $P_1$ was the real/ideal interaction, or if $(0,0,0)$ with the message $0$ from $P_1$ was the real/ideal interaction.


texts: Why does NIST say that 2nd preimage resistance depends on the message length

texts:
In NIST FIPS 202 on the table, It is written as

Function
Output Size
Collision
PreImage
2nd Preimage

SHA-1
160
< 80
160
160–L(M)

SHA-224
224
112
224
min(224, 256–L(M))

SHA-512/224
224
112
224
224

SHA-256
256
128
256
256–L(M)

SHA-512/256
256
128
256
256

SHA-384
384
192
384
384

SHA-512
512
256
512
512–L(M)

with $L(M) = \lceil \log_2(len(M)/B) \rceil$ where $B$ is the block length of the function in bits, i.e., B = 512 for SHA-1, SHA-224, and SHA-256, and B = 1024 for SHA-512.
For the discussion directs to NIST 800-107r1. and it is on the appendix;

The actual second preimage resistance strength for SHA-1, SHA -224, SHA-256 and
SHA-512 is approximately $(L – M)$, where $L$ is the output block size of the hash function,
and the message is $2^M$ input blocks in length.

For example, if a message that is $2^{33}$ bits in length (i.e., a gigabyte long) is hashed by
SHA-256 (whose input block size is $2^9$ bits), the second preimage resistance strength is
$(L – M) = (256 – 24) = 232$ bits (where $L = 256$, and $M = \log_2(2^{33}/2^{9}) = (33 – 9) = 24).$ That is, the amount of work required to find a second preimage is $2^{232}$.

It is important to note that the amount of work is based on the number of compressions
function executions (compressing single message blocks), not on the number of hash
function executions (hashing messages of more than one block in length)

First of all, there is no reference for this claim. Is there any reference for this claim?
Is there a better explanation for this attack?


texts: Measuring entropy of a uniform distribution source

texts:
What is entropy? I do not understand it at all.  One article states:

When there is an equal chance for all items to appear, we have a
uniform distribution. In uniform distribution the entropy is high.

I'm confused. If entropy is high, we should consider that disorder is high too, but in a uniform distribution we don't have disorder because all items have the same chance to appear.
Is it possible for someone to explain entropy in cryptography and make this concept clear for me?


texts: Is obfuscation considered a cryptographic primitive?

texts: The general definition of obfuscation is the process of obscuring a message (not necessarily source code). There is a "rigorous" method for obfuscation (indistinguishability obfuscation, extractability obfuscation) and a less rigorous one (spaghetti code, antipatterns, seldom used languages behaviours, ...). But is obfuscation a type of cryptographic primitive?


texts:
Let's say we have some very sensitive personal files.  At all costs, we do not want any other pair of eyeballs to gaze upon them.  We need these sensitive files to be secure and available.
So, we have a bright idea: encrypt them and put them in the Cloud.
What side-channel attacks, if any, are specific to Cloud storage?
For example, could various Cloud-storage providers accidentally introduce weaknesses?


texts: Is it possible to insert a key derivation function when using EAX?

texts:
I am currently investigating use of EAX mode for a dedicated application and following useful clarifications received from my previous post , to consider according to my applicable input security requirements (separate keys for encryption and authentication) either :

the  Baseline solution where EAX is used in strict respect of its
specification and so with one unique key K
or an eventual (only if it has a sense) alternate solution with insertion
before EAX, of a key derivation function allowing to generate from
the unique input key K, one KA key for OMAC functions and one KE
key for CTR function

Can such alternate solution be envisaged or may it violate EAX mode specification and associated security proof ?


texts: What key exchange protocols give Forward-Secrecy resisting future progress?

texts:
I (wrongly) understood what I've been told as meaning DHE in TLS, PFS in IPSec do not provide Forward-Secrecy; and I'm told that common forward-secure key exchange protocols are restricted to establishment of an Asymmetric key, or are otherwise vulnerable when the security of some security assumption of an asymmetric cryptosystem collapses.

I ask which (preferably well-studied) key exchange protocols (if any, which I have now come to doubt) provide the following enhanced form of Forward Secrecy, for exchange of a wide ephemeral symmetric key, by mean of some asymmetric private/public key pairs; in the sense of insuring that an intercept made at a date when the assumption(s) of hardness underlying the asymmetric protocol(s) used holds, can't help recovering the ephemeral symmetric key established, even after said assumption(s) of hardness no longer holds.

Note: I now realize that collapse of assumption of hardness of all asymmetric cryptosystems is a stronger assumption than compromise of the long term private asymmetric keys, which is the standard assumption in forward-secrecy.


texts: Significance of 3mod4 in squares and square roots mod n?

texts: Why do most literature while discussing squares or square root modulo a prime P, consider P to be congruent to 3 mod 4?


texts: Making a cipher non-malleable using a plaintext transform?

texts:
NOTE: By malleable/non-malleable, I mean the ability/or not to change a byte/block of the ciphertext and have it change only that byte/block of the plaintext.
I understand that we use authentication (via HMAC/UMAC/etc.) to verify integrity. However, where authentication is not possible (perhaps in a case where one has a very limited environment on storage/CPU power), can we transform the plaintext before encryption?
Using several "rounds" of a move-to-front transform that reverses the plaintext after each iteration does exactly that. Once the plaintext is over 1kb (or so), you only need a few rounds. This creates a sort of avalanche effect' so that tampering in any place affects a large amount of the plaintext.
My MTF transform uses an index of possible bytes (0-255). Each "round" consists of an MTF transform, resetting the index, reversal of the plaintext, and another MTF transform.
Running some tests suggests that with two rounds of my MTF for random 256-byte inputs, flipping any bit will, on average, change over 50% of decoded bits. For a 512-byte input, the average is 53%. For a (barely tested) 1024-byte input, the average (and lowest) number of bits changed is over 50% for any flipped bit.
The outliers (minimum number of bits changed) are linear for small enough inputs. For a 512-byte (or less) input, the lowest number of bits changed is always achieved by flipping the first bit (further right) of the first input byte. Additionally flipping any bits at the end of a small input always results in a greater than 50% change, but not at the beginning. These undesirable effects seem to disappear with a 1024-byte input, although testing this takes me too long (about 2 minutes per input!) to make any useful statement.
The main problem with this approach is that it takes too long. I am using a small notebook with Intel Atom CPU Z3735 @ 1.33GHz. One KB takes around 0.034 seconds to encode. To encrypt a KB using ChaCha takes around half this time.
NOTE: The transform function is completely known (per Kerckhoff's principle). It is completely dependent on the plaintext. The function does absolutely nothing except add non-malleability to the plaintext and thus ciphertext. It works before ANY cipher, and not with.
UPDATE: I've updated the transform function, altering the indexes used for the transform rounds, reducing the rounds to 2, and adding a running sum of data input to the process. It is now quicker than ChaCha and achieves non-malleability at 512 bytes of input, without any bias (within limits of my testing). It adds a nonce on encoding that it removes on decoding. The code is here if anyone wants to have a look.
I'm aware I could make the code faster, but I still think there must be some standard approaches to the overall problem. The only modern, similar thing I've found relates to an all-or-nothing transform, which Rivest discusses here. It seems strange that the idea (assuming Rivest is correct about added security) didn't really catch on.
My questions:

Is there any existing approach that does anything similar to this? Basically some sort of modern version of Russian copulation?
Does anyone know a potentially quicker way to transform plaintext (completely independent of the cipher) and make it (potentially) non-malleable?


texts:
I'm working on a Java authentication subsystem that specs the storage of passwords in the DB as PBKDF2-generated hashes, and I'm now trying to decide whether I should use SHA1 or SHA512 as PFR. I'm under the impression that the consensus is that SHA1 has some theoretical weaknesses, and that SHA512 should be chosen instead. However the standard javax.crypto package does not offer a PBKDF2WithHmacSHA512 implementation, how is that so?

For reference purposes, here’s my code:

private static final int HASH_BYTE_SIZE = 64; // 512 bits
private static final int PBKDF2_ITERATIONS = 1000;

// generate random salt
SecureRandom random = new SecureRandom();
byte salt[] = new byte[SALT_BYTE_SIZE]; // use salt size at least as long as hash
random.nextBytes(salt);

// generate Hash
PBEKeySpec spec = new PBEKeySpec(password, salt, PBKDF2_ITERATIONS, HASH_BYTE_SIZE);
SecretKeyFactory skf = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA1"); // this throws a NoSuchAlgorithmException if I replace with "PBKDF2WithHmacSHA512"
byte[] hash = skf.generateSecret(spec).getEncoded();

// convert hash and salt to hex and store in DB as CHAR(64)...


texts:
Recently, I am learning the Oblivious Transfer (OT) Protocol. I have some questions about the OT extension. In ALSZ13, we know that $m\times OT_l$ can be reduced to $\kappa\times OT_\kappa$, where $\kappa$ is a security parameter, $l$ is secret's bit length. So my question is:

How can I implement $\kappa\times OT_\kappa$? Is it run $OT_\kappa^1$ protocol $\kappa$ times? If yes, is $OT_\kappa^1$ same to NP01 Protocol 3.1 says that $OT_1^N$?


texts: Post-quantum SNARGs with near-constant verification?

texts:
We're building a private computation platform similar to Zexe, where nested proofs are used to preserve the privacy of the programs being computed. We may use different proof systems for the inner and outer proofs. For the inner proofs, we're searching for a system with these properties:

Conjectured post-quantum security, which rules out Groth16 etc.
Constant or near-constant verification time. Logarithmic would be okay, but polylogarithmic (like STARKs) would be undesirable. If verification was polylogarithmic, we'd probably want multiple verification programs to handle different ranges of proof sizes, and the verification program being used for a computation would leak some information about the kind of computation being done.
Non-interactivity.

We don't need a zero knowledge property; that would be redundant since privacy is already protected by the outer proof system.

I believe the PCP theorem implies that it's at least possible to get logarithmic proof sizes (in the QROM), by transforming a PCP scheme into a sigma protocol, then applying Unruh's transform for non-interactivity. If we used a Merkle accumulator for commitments in the sigma protocol, the SNARG would consist of a constant number of log-sized Merkle paths.

Is this reasoning correct? Are there any practical proof systems with these properties?