texts: Understanding definition of secure pseudo random number generator

texts:
From my reading, a secure pseudo random number generator is called secure if, given a sequence of numbers generated by the PRNG, then if any one of those numbers from the sequence is removed an adversary could not determine the removed number via any method better than guessing.  Of course the existence of such secure PRNG's is unknown.

Reading such a definition however, I am unclear on a couple of things.  Assume $G$ is a pseudo random number generator so that an adversary could not determine the missing value in a sequence by any more efficient method other than guessing.  But also assume the output of $G$ is normally distributed: Then the adversary may still have to guess to determine the missing value, but with high probability the missing value will be in a particular interval.  Would such a PRNG still be called secure?


texts: Does encrypting with MGF1/SHA-512/1024-bit seed equal to a 1024-bit key block cipher?

texts:
Suppose:

Alice uses SHA-512 with MGF1(as in PKCS#1 V2) and a 1024-bit random seed to generate a mask, XORs the mask with a message(M), gets a cipher text (CT), and sends the CT to her old friend Bob. Of course, curious Eve is listening...
Alice and Bob exchange the seed in a secure way (while Eve sleeps and does not know about it); they do not care about the speed of this algorithm.

Questions:

Is CT as secure as being encryted by a 1024-bit block cipher?
Why?


texts:
It is my understanding that PRNGs typically use a seed and can then generate random values one after the other. This is what I mean by being 'sequential'.

How about a PRNG which allows me to retrieve e.g. the third value, without computing the first and second? Basically, I'm looking for a function $g: \mathbb{N} \rightarrow (\mathbb{N} \rightarrow \mathbb{R})$ such that for all seeds $n \in \mathbb{N}$, $g(n)$ is a function who's values follow some specified distribution while computing $g(n)(m)$ takes constant time.


texts: Why is it allowed to Generate Keys inside the game?

texts:
I am studying reductions to prove security of crypto systems. Generally "games" are used for the proofs. For example, the next image was extracted from the page 91 of the book Post-Quantum Cryptography. Here, an adversary is constructed against Lamport-Diffie signature using a Forger with access to an oracle.

My question is why is it permitted to the adversary to generate keys? I make this question because the step 1 of this Algorithm calls the key generation process.


texts: What exactly is the impact of the hidden subgroup problem on cryptography?

texts:
I understand my group theory (allegedly), so I can make partial sense of The Hidden Subgroup problem:

  Given a group $G$, a subgroup $H \leq G$, and a set $X$, we say a function $f : G \Rightarrow X$ separates cosets of $H$ if for all $g_1, g_2 \in G$, $f(g_1) = f(g_2)$ if and only if $g_1H = g_2H$.

  Hidden subgroup problem: Let $G$ be a group, $X$ a finite set, and $f : G \Rightarrow X$ a function such that there exists a subgroup $H \leq G$ for which $f$ separates cosets of $H$. The function $f$ is given via an oracle. Using information gained from evaluations of $f$ via its oracle, determine a generating set for $H$.

In English as much as possible, $G$ is a group which means it satisfies certain conditions such as there being an identity and inverse element under an operation. Here, the operation isn't specified. So then we have some set $X$ which does not necessarily have to meet these criteria, and $f$ a function that maps $G$ the group onto $X$.

Cosets e.g. $gH$ are the set of all $H$ operated on by a specific $g$, so $gH = {gh: h \in H, g}$. $Hg$ is the other ordering and exists because groups aren't required to be abelian.

So this splitting function $f$ ensures each coset is mapped uniquely if when the function is applied to the group members it and derives the same result, when applied to the relevant cosets it must also derive the same result. This establishes that each coset does essentially map to a unique set of elements in $X$ if I understand this correctly.

So, the HSP is essentially the task of finding $H$ given $G$, $f$ and $X$ if I follow that correctly.

So, the obvious one-way-problem great-if-you-know-$H$ issue aside, how does the HSP affect cryptography? Specifically, aside from the discovery of the set $H$ in $X$ I see no particular direct use for the HSP, yet I have come across it frequently in discussions on cryptography, particularly with the odd link or reference towards this paper. Finally, am I missing anything, aside from the impacts of cryptography, in my summary of the HSP?


texts: Are there any issues to doing 2 rounds of AES-128? How is the security compared to AES-256?

texts:
I have a SoC with hardware AES-128 encryption, which is obviously quite efficient in terms of power usage and memory used. However, we would like to have AES-256 encryption (half for commercial reasons, half for post-quantum security).
To achieve this, we consider:

Using software encryption (which will be slower, use more power, and at the least require more code and hence flash space).

Using 2 rounds of AES-128 one on the other, with different keys, effectively giving us a key length of 256 bits.

I am aware that 2 round of 128 bits is not the same as 1 round of 256 bits, but as I'm not an expert, I was wondering if anyone knows about drawbacks or vulnerability introduced by such practice, and ultimately if this would be equivalent to the security brought by AES-256 (ie, take a similar amount of time to break the encryption).
Also, I use AES CTR. The planned implementation would be create 1st cypher block, XOR it with 2nd, and XOR this with the plain text.


texts: What MAC did SSLv3.0 use? How did it compare to HMAC in TLS 1.0 and above?

texts:
According to Wikipedia:

TLS has a variety of security measures:
Using a message digest enhanced with a key (so only a key-holder can
check the MAC). The HMAC construction used by most TLS cipher suites
is specified in RFC 2104 (SSL 3.0 used a different hash-based MAC).

What hash-based MAC did SSLv3.0 use?  How does it compare to the ubiquitous HMAC that is used everywhere else today?


texts: Audio Files and Digital Bearer Instruments

texts: Is it possible to combine Audio Files and Public Key Cryptography creating a Digital Bearer Audio File that is in complete control of the owner who would then have the ability to grant access to listening to the file, editing the file and sharing the file?


texts: Orignal Krawczyk's HKDF vs latest NIST SP800-56C

texts:
I've noticed that the original HKDF in rfc5869 defines a feedback loop. So the pseudo-code is something like:

for i = 1...n
    out[i] = HMAC(key, out[i - 1] + i + info)

However, the NIST recommendation 800-56C seems to only depend on a loop counter for each round:

for i = 1...n
    out[i] = HMAC(key, i + info)

From a security perspective, is there any significant weakness if we don't do the feedback loop?


texts: Is it possible to use structures other than finite fields?

texts:
I have some difficulties to understand why we are using finite fields in cryptography.

Why do we use field? Why not ring or group? Is that really necessary that the field is finite? Why not real field?


texts: How does Flatten really make the coefficients of a vector matrix small in LWE

texts:
In Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based, Gentry et. al defined Flattening as follows;

Let $\vec{a},\vec{b}$ be vectors of some dimention $k$ over
$\mathbb{Z}_q$. Let $\ell = \lfloor \log_2q \rfloor +1$ and $N = k
 \cdot \ell$
Define $\operatorname{BitDecomp}(\vec{a})$ be the $N$-dimentional
vector $ = (a_{1,0},\ldots,a_{1,\ell-1} \ldots,a_{k,0},\ldots,a_{k,\ell-1})$, where $a_{i,j}$ is the $j$-th
bit in the $a_i$'s binary representation, bit ordered least
significant to most significant.
For $\vec{a}' = (a_{1,0},\ldots,a_{1,\ell-1},  \ldots,a_{k,0},\ldots,a_{k,\ell-1})$, let
$$\operatorname{BitDecomp}^{-1}(\vec{a}) = (\sum 2^j\cdot a_{1,j},
 \ldots, \sum 2^j\cdot a_{k,j}) $$ be the inverse of
$\operatorname{BitDecomp}$, but well defined when the input is not a
$0/1$ vector.

This is nothing but usual decomposition into bits and the data has already stored in the decomposed way.

For $N$-dimensional vector $\vec{a}'$, let $\operatorname{Flatten}(\vec{a}') = \operatorname{BitDecomp}(\operatorname{BitDecomp}^{-1} (\vec{a}'))$.
When $A$ is a matrix, let $\operatorname{BitDecomp}(A), \operatorname{BitDecomp}^-1(A)$, or $\operatorname{Flatten}(A)$ be matrix formed by applying the operation to each row of $A$ seperately.
An interesting feature of $\operatorname{Flatten}$ is that it makes the coefficients of a vector matrix $small$ without affecting its product with $\operatorname{Powersof2}(\vec{b})$, and without knowing of $\vec{b}'$

It is not clear for me how the $\operatorname{Flatten}$ makes the coefficients of a vector matrix $\boldsymbol{small}$. What I see that the two operations, $\operatorname{BitDecomp}$ and $\operatorname{BitDecomp}$, are just the inverse of each other. Could someone elaborate on what I'm missing here?


texts:
I have some doubts regarding the SET protocol. Let say the Alice payment information runs through a sha-1 hash function which is a one-way algorithm, irreversible to create a message digest. How do bob verify that the message is really from alice since he can't see the content of the message which bob shouldn't see in the first place?

Based on my understanding, it has something to do with public digital signature and comparing it with the message digest but I don't get it. Can anyone explain the concept to me in layman terms.


texts: Cryptography elements needed for a story

texts:
Note: following Maarten Bodewes's answer, I edited this post to make it clearer.
I'm writing something partly driven by the need to crack a few encrypted files.
This is what needs to happen in the story:
There are two parties involved that are trying to crack them, party A and party B. Party A has had them for four years, and despite all attempts, they failed. Party B got the files later on and managed to crack them in less than two months of non-stop trying.
Party A has available state-of the-art tech, but party B are the good guys and this is a sci-fi story, so they have far, far better tech that nobody else has. The details of the technology aren't relevant to the story so I don't need to establish them.
Party B will eventually succeed; still, to keep a modicum of suspense up, it must still be possible for them to fail. By this I don't mean that something throws a spanner in their works; I mean that their decryption attempt, however more advanced than party B's, isn't guaranteed to work. In other words, party B can't just sit and wait until whatever they're doing is done knowing that at that point they will have the decrypted file.
This is what I need:

An algorithm such that, if you encrypt a file with it using a high-entropy password, is beyond any brute-force attempts using known methods and tech. (This is why party A fails.) I understand that AES-256 might be what I'm looking for.
An approach that will allow party B to succeed nonetheless. The fact that party B has much faster computers available than anyone on Earth is central to the story so you can assume that. However, if brute-forcing these files required ridiculous amounts of energy or other very unrealistic things, I'm not prepared to claim party B has any of that. Other approaches or situations that would give party B an edge—such knowing what algorithm was used, being able to guess details about the password, or knowing about possible key files—are certainly options I would consider. If quantum computers could plausibly break AES, that's another option I would consider because it's not too far-fetched for party B to have them. I just don't know if QC could actually do that.


texts:
I often encounter the term “security parameter” when I read crypto related stuff. My basic understanding is that it just denotes some bit-length however, I'm not so sure.

For example, when it says

  … output strings of length 2K where K is the security parameter

how should I understand that ?


texts: What's the perfect chain length : number of chains ratio for rainbow tables?

texts:
I'm building a SHA-1 rainbow table to crack basic passwords (i.e. up to 10 character, 0-9,a-z), but I can't seem to calculate that golden ratio that would give me the most coverage. What ration of chain length to number of chains should be chosen?

Also is there anyway to estimate the coverage of the table? As at now, after building the table I'm using a brute-force attack to check it's coverage. It's a very inefficient way.


texts: Where to store the file extension to retrieve it correctly after decryption

texts:
I am using Java to write AES-256 to encrypt various files with different extension, the problem is, where am I suppose to store the file extension so the if the data is decrypted, the file extension would be restored ?

For example,

If I encrypt a "test.pdf" file, I will first read it as a byte array and then encrypt it using AES-256, but when the data is decrypted, I can manually save the decrypted data as "xyz.pdf", but this is because I know the original file extension was "pdf".

What If I don't know what was the extension of the original file before encryption,
If I save the extension inside the encrypted text, then It would only be decrypted with my AES algorithm and wouldn't be decrypted with any another AES-256 algorithm even if the user has a correct key.

So, Where Am I supposed to store the extension of a file?


texts: Distortion of the spherical gaussian error through the canonical embedding in Ring - LWE

texts: In the paper, "On Error Distributions in Ring-based LWE" by Castryck, Iliashenko and Vercauteren, page 3, It is shown that the distrotion to the spherical gaussian in Ring - LWE is caused by the inverse of the vandermonde matrix and the matrix of multiplication by f'(x). It is explicitly stated that the inverse of Vandermonde matrix B is converted into a real matrix by a "easy unitary transformation". Can anyone help me out in figuring how get such a unitary transformation that takes a complex matrix to a real one?


texts: Burmester Desmedt confused on the last step

texts:
I try to implement in code the traditional burmester desmedt algorithm for group key agreement:

But I have the following question regarding the last step:

$K=k_{i-1}^{nx_i}K_i^{n-1}K_i+1^{n-2}\dots K_{i-2} \pmod p$

But when it comes down to boil into code I find hard time to understand what operations are actually executed

First of all does the $K_i^{n-1}$ is resulted in pseudocode as mentioned bellow?

value = participant.length-1
power(participant[i].K, participant.length-1)

Where power is raising into power participant[i] represents the ith participant and participant.length-1. Also should execute the execution above until until value it turned into 0 meaning:

 value = participant.length-1
  index=i
  do {
     power(participant[index].K, value)
     index ++
     value --
  } while(value=0)

Also after that what other calulations are required I mean there also a $K_{i-2}$ how after that I will what loop do I need to execute should I just iterate through Calculated $K$ values for each participant and just multiply them from i to i-2 in reverse order?


texts: About the scalar multiplication on Koblitz curve in FIPS PUB 186-4 (2013)

texts:
In FIPS PUB 186-4, the computation of scalar multiplication on Koblitz curves is given in p.106~109. In p.109, step 11.3, $(r_0,r_1)$ is updated with $(r_1+\mu\,r_0/2,-r_0/2)$. But under certain case, when $r_0$ is even, $\mu=-1$, then the while loop 11 will never stop.

How can this be overcome?


texts: If a SHA256 hash with high entropy is then hashed with one made from low entropy, is the resulting hash higher/same/lower entropy?

texts:
If one were to create a SHA256 hash using 256 coin flips converted to hex (which, as I understand it, is as "entro-phized" as one can capture in SHA256) then take that hash as a string, combine that with a hash of the word "cat" and hash the resulting 512 character string, would the resulting hash from that exercise be any less random than our "perfect" hash we began with?

My thinking is the final string would capture the same amount as the original randomness as what we started with because the "extra" entropy can not be captured and is lost. Is this the case and am I thinking about this correctly? Would hashing something with high entropy with something simpler ever cause a lower amount of randomness or does it only go up?

Thanks to anyone who can help explain this a little better.


texts:
i read about linear cryptanalysis and about S-Box that there is not any ideal S-Box (ideal S-Box is a random S-Box in another words S-Box that bias of input and output bits is zero) then i read about implementation of S-Box in this post and understand that S-Box is implementing with Lookup tables,then read this post (e-sushi's answer) about non-linearity and randomness aspects of S-Box:

  And you can trust in the fact that the chances that you’ll manage to create a good s-box randomly by using your current criteria are very minimal… very, very minimal!

but i don't understand that why is not there any random(ideal) S-Box? why can't lookup tables implement a random S-box? what is restriction(limitation) for it?


texts: Do random oracles are called even by honest users in the PAK protocol [BMK00]?

texts:
In the full-length proof of PAK scheme, the authors made extensive use of random oracles to extract (guessed) password from the messages generated by the real world adversary for the ideal world simulator.

Questions:

Are all the random oracle calls $H_i(\cdots)$ in the real world protocol (even called by honest users) controlled by the simulator?
Does the simulator need to make responses for the requests of honest users via the real world adverary's delivering?
Does the simulator make use of the status of honest users? For example, A (either the honest user or impersonated by the real world adversary) sends a password to B and B sets the status of himself as accept or reject. Is B's status watched by the simulator and the real world adversary?
Why the password-extraction from real world messages is so imporant in simulation-based proofs? Is it indeed some kind of zero-knowledge proof for showing these password-related messages in the real protocol are as zero-knowledge as the messages in the ideal world? (as the authors suggested to use NIZK in place of random oracle)
Is there any weaker proof method (which, however, still guarantees us security practically), especially for the password-authenticated key exchange area?


texts: Implementing secret reconstruction in Shamir's Secret Sharing

texts:
I am trying to implement Shamir's secret sharing in C++.
I have got the generation of shares working.

However, I am very confused with the reconstruction of shares. I get the part on how three users can reconstruct the secret. But what if there are more than 3 users needed to reconstruct the secret? How do I implement the formula then?

Any help would be appreciated.


texts: Man-in-the-middle attack on Diffie-Hellman with shared public keys?

texts:
Is it correct to say if the public key is known to all users beforehand,  Diffie-Hellman key exchange is not vulnerable to man in the middle attack?

Sample key exchange ( assuming all users public key is known ) :

\begin{align}
  A \rightarrow B &: Y_b^{N_a} \\
  B  \rightarrow A &: Y_a^{N_b}  \\
Shared Key  &= g^{N_a+N_b}
\end{align}

Where $N_a$ is random int generated by $A$
and $Y_a$ = $g^{S_a}$ where $S$ is the secret key generated by $A$.


texts: Needed: signature over a collection of hashes

texts:
I'm looking for some kind of crypto-based data structure that will allow me to produce a signature over a set of hashes. Call this a SignedSetOfHashes. I want to be able to distribute the SignedSetOfHashes (which should be smaller than simply a vector of all the hashes and a digital signature.) I then want anyone to be able to verify that hash H is in the SignedSetofHashes having only the SignedSetOfHashes and a public key that matches the private key used to create the signature.

One idea I had was multiplying all of the hashes together in a field and signing the residue. Then I could verify any of the hashes are in by showing that the residue is divisible by any of the hashes. Of course, I could verify the signature without having any of the hashes.

Is there an existing approach to do this?


texts: Any suggestions for A Proof-of-Work algorithm in literature so that the time required for solving it is linear with the puzzle difficulty ??


texts: What is shared-input for Multi Party Computation?

texts:
I heard shared input.
For example, original values $x,y \in M$ are divided into pairs of shares $(x_1,x_2)$ and $(y_1, y_2)$ such that $x_1 + x_2 = x \text{ and } y_1 + y_2 = y$.
Each share is distributed to two parties $P_1$ (who obtains $x_1$ and $y_1$) and $P_2$ (who obtains $x_2$ and $y_2$).

When $M = \mathbb{Z}_2$, addition is just XOR computation.

With additive shared input, can any computations be evaluated??

If so, what is the method used for the evaluation??

Is garbled circuit applicable to this scenario??


texts:
I am just beginning to read into pseudorandom generators and I came across this definition for a PRG:
$G_n : \{0,1\}^n \rightarrow \{0,1\}^{l(n)}, \quad \text{ where $l(n)$ is a polynomial}$
Is there a reason why $l(n)$ has to be polynomial? Wouldn't there be an even better security guarantee if it was an exponential function? Simply because the adversary in the definition of pseudorandomness also is a probabilistic polynomial-time adversary.


texts: Is there a name for encryption which relies on repetitive calculation (=time) instead of a key-value? (e.g. block chain, hash value, block cipher)

texts:
Many encryption problems are fast to solve if a key, factor, exponent or something similar is known.
Other encryption methods don't have such keys. E.g. a hash value of another value. It's used because it is hard to determine which was the initial value. Computation time is needed for the solution. Is there a general name for this?

Especially I'm looking for methods which generate a chain. Starting at one value and computing the next value over and over again. Given two random values it should be hard to determine how many calculations are in between them. Is there a name for this?

In addition to the next value also the previous value should be computable in about the same time. Symmetric  block cipher encryption is close to. But is there a more general name which is not limited to 'blocks'. Also different functions can be used for forward and backward direction.

Optimal case would be if besides next and previous element also selective offsets can be computed efficient but all other not. Is there a name for this?


texts: Why $\alpha$ in ElGamal cryptosystem has to be a primitive root?

texts: When choosing the public key for ElGamal, $\alpha$ must be chosen as a primitive mod p. What if $\alpha$ is not a primitive root ? How will it influence the encryption and decryption ?


texts: zero knowledge proof of range and set membership

texts:
I have a large number of items with a unique serial number and a score (score isn't always unique).

There is a list which contains all of the serial numbers and their respective scores.

I select 3 items at random, and have to prove:

That all three items are in the list
The total of the scores exceeds a predefined global number X

This has to be done without revealing what the original serial numbers or scores were.

All the answers I've seen haven't been applicable to this scenario because they all seem to rely on the fact that a list is a group that has generators, but my list isn't.


texts: Converting a stream cipher into a block cipher

texts: The well-known Counter-Mode (CTR) mode of operation for a block cipher essentially converts any block cipher into a stream cipher.  Is there a way to do the reverse?  In other words, given a "good" stream cipher $G$, can we construct a block cipher that builds its strength based on $G$?


texts:
have few more questions about disk encryption with AES cipher:

Do we consider all zeros (0000000) as empty block of data or is it still a data?

Do we really need padding to the data blocks if a disk sector is multiplication of data block?

Also if one data block is empty (all 000000) why we just dont apply encryption on that block as usual?

Most of the disk encryption software let us to encrypt used space vs full disk. In case of full disk , how is the empty space being encrypted with AES?

is disk encryption always encrypt data into same location? lets say data from sector 200 will always land after encryption in sector 200? (assuming that we are not adding any HMAC which expands the data).

Does AES keep track which sector of disk is encrypting? Or this info is irrelevant for encryption? I think bitlocker in CBC mode adds IV as encrypted sector number - but is it to keep track on sector number or just to randomize the input (instead of sector number they could just add any random number)


texts:
I've just come across the large variety of encryption ciphers available in the UWP WinRT API, both symmetric and asymmetric. I'm trying to figure out which are commonly seen as the most favourable from the choices available for UWT (obviously this is very context specific, but surprisingly many seem to be outdated or clearly just "worse").

With symmetric, I've seen that AES is usually a good go-to algorithm of choice (this post for example), and this site says AES_GCM is pretty much the best variant.

With asymmetric the two main options presented in UWP's API are ECDSA and RSA. I was sceptical if ECDSA was actually an encryption algorithm, but this answer certainly made it seem so, even if the name says "digital signature". Now all of these names include a hash, and their descriptions state that there is signing involved with this hash, which confused me. Why is this explicit encryption algorithm signing this stuff too?
Anyway, this post, and this article both suggest that OAEP is better than PKCS#1, which then leaves us with the following options for asymmetric encryption:
ECDSA_P256_SHA256
ECDSA_P384_SHA384
ECDSA_P521_SHA512
ECDSA_SHA256
ECDSA_SHA384
ECDSA_SHA512
RSA_OAEP_SHA1
RSA_OAEP_SHA256
RSA_OAEP_SHA384
RSA_OAEP_SHA512
Given that P256, P384 and P521 are the public key size for ECDSA, then that raises the question of what the difference is with the ECDSA without P256, P384 or P521? What applicable difference do these differences make?

Okay, cheers for reading so far! I've summarised my questions below:

Is the assumption that AES is "best" a valid one, alongside the assumption for AES_GCM?
Is ECDSA actually an encryption algorithm, given the name?
Why do the UWP API asymmetric encryption algorithms all reference signing with hashes in their descriptions? Is this really the case, and if so why? Surely if they wanted authentication through signing it would be a separate process?
Is OAEP generally considered better than PKCS#1?
What is the difference between the ECDSA algorithms which do and don't specify public key size (eg ECDSA_SHA256 vs ECDSA_P256_SHA256)?
What difference do the hash sizes (and public key sizes for ECDSA if relevant) make, and what about if authentication isn't needed (which I guess would be why they're hashing and signing in the first place)

Any and all help is greatly appreciated, thank you for your time! :D


texts: What signature schemes allow for a space efficient multisig? Any that also allow others to easily add to an existing signature?

texts:
For instance, Is there a scheme where 100 people could produce a signature that is only as long as one signature?

Is there one like this that can be done where each person can merely modify an existing signature to add theirs to an existing group signature without the group's cooperation?


texts: Provable Lower Bounds for some Algorithmic Problems?

texts:
Are there any problems for which we have known lower bounds?
For example, for comparison based sorting, we know you need $\Omega(n \log n)$ comparisons.
Edit: I'm aware that this requires restricting the algorithm to comparisons. I couldn't think of any lower bound in an unrestricted model, but I'm mostly interested in lower bounds for unrestricted computations.
My motivation for this is: while we don't know how to prove that one-way functions exist, maybe we don't need that to achieve at least some provable polynomial separation between evaluating a function, and reversing it. Even a problem with $\Omega(n^7)$ could suffice to build somewhat practical cryptography: $c \cdot (2^{128})^{\frac{1}{7}} \approx c\cdot319557$ bits (for some constant $c$) would be required to obtain the same security level as a 128 bit key.
Does this question make sense? If not, where do I go amiss? Do my calculations make any sense?


texts: Proof of shared secret through key derivation

texts:
Alice gives a random key $K$ (e.g. 32 bytes long) to Bob through a secure channel.

Bob want to prove to Alice through an unsecured channel that he knows the key.

Is it secure for Bob to send $s||KDF(s||K)$ −with $s$ a random tag, say 8 bytes long− ? It seems Alice can recompute $KDF(s||K)$ and compare. Nobody can deduce K from the message.
Provided tags are one time use only, and Alice keeps track of which have already been used, how many different proofs could Bob send before an observer could potentially figure out K ?
Is there a way to improve that function ? Any specific key word, name of algorithm or protocol about that topic ?

Edit : I understand HMAC is the function I am looking for. Is it safe to use it for that purpose ? Can an observer learn anything about the key from many HMAC ?


texts: Does AES CTR mode store header information in encrypted files?

texts:
According to the movable-type.co.uk website,

  In the ‘counter mode’ used in this implementation, a counter which changes with each block is first encrypted, and the result is bitwise xor’d with the plaintext block to get the ciphertext block (so the plaintext is not actually directly encrypted). A unique ‘nonce’ is incorporated in the counter to ensure different ciphertexts are always generated from the same plaintext every time it is encrypted; this number is stored at the head of the ciphertext to enable decryption. A combination of seconds since 1 Jan 1970, a millisecond-timestamp, and a sub-millisecond random number gives a very effective nonce. (To resist cryptographic attacks, the nonce does not need to be secret or unpredictable, but it is imperative that it is unique). In this implementation, the initial block holds the nonce in the first 8 bytes, and the block count in the second 8 bytes…

So, it says that the “nonce is stored in the cipher text to enable decryption”. Is that true for every AES CTR mode implementation? And if we want to decrypt a certain block from the middle, do we first have to extract the nonce from the first 8 bytes and the block count from the following 8 bytes?


texts:
Is it possible to combine SHA1 digest values to get the SHA1 of the concatenated parts ?
I know the "S1" SHA1 of "part 1" and the "S2" SHA1 of the "part 2" and I would like to know the SHA1 of the "part 1" concatenated with "part 2" calculated from "S1" and "S2".

Is it possible ?


texts: Build set with PKI from reliable broadcast / random beacon

texts:
I am trying to build a protocol (or find an existing one) for creating a set $S_2$ with PKI from a set of parties $S_1$ that initially does not know anything about the other parties.

We assume end-to-end communication and broadcast, all with a delay up to $\text{Delta}_\text{transmission}$. Additionally, we also use NIST random beacon (could simplify the protocol, but it doesn't solve the deadline problem below).

So every party $p \in S_1$ would run this protocol $A$ at a time $t_1$, and we would like at $t_2$ that all honest parties have the same set $S_2$ of parties with PKI.

I could imagine a solution where all parties generate a private/public key pair, and then the protocol dictates that for each round, they broadcast a signed message with their public key and current vision of $S_2$; ie $m = [pk, S_2]$.

each time they receive a valid signed message with a new public key $pk'$ and a new set $S_2'$, they do $S_2 = S_2' \cup S_2 \cup {pk'}$, and rebroadcast $[pk, S_2]$

The main problem with this scenario is termination : if we want the protocol to terminate at any deadline $t_2$ fixed in advance; there is always a way for an attacker to break consistency (all honest parties have the same set $S_2$ in the end) by sending a new valid message $m'$ just before the deadline to a party $p$, so that this party accept it, but when the honest party rebroadcasts his new set including the new key, other honest parties discard it because it arrives after the deadline $t_2$.

Any help, either directly on how to fix the deadline problem, or indirectly how to build such protocol, would be greatly appreciated :)


texts: Key strenth in Cipher cascades (Veracrypt)

texts:
Disclaimer : basic crypto knowledge

So this is a question specificly about veracrypt , but theoreticly applies to any other encryption software which supports cipher cascades .

So if you use a cipher cascade with 3 cipheres e.g : AES(TWOFISH(SERPENT)) , then the key is divided in 3 different keys (hashes from KDF ) with 1/3 of the original key strength . So like a 8-10 charakter long password would not be considered secure right ?

But what if you use a keyfile like some mp3 file or some random generated stuff like an RSA cert. Veracrypt uses the first 1024 byte of the file so that would make a 4096 bit master key and a 1365 bit key for every cipher in the cascade if I understood that right.  Which would be more than enough to be secure right?

Please correct every misunderstanding in my previous claims.


texts: Designing of Password Authenticated Key Exchange (PAKE) Schemes?

texts:
I am started working in post quantum cryptography(lattice based cryptography) specifically in Password Authenticated Key Exchange (PAKE). I come across many PAKE key exchange scheme (like this one) that do not take in consideration the registration process and login process. These schemes simply assumes that two parties are sharing some secret password of low entropy  and based on that they will generate common session key. So, my question regarding PAKE techniques are

  What is the scope of PAKE schemes? Is Registration or Login process should not be considered while designing the PAKE key Exchange schemes?


texts: Decoding an MD5 hash where I already know most of the string

texts:
Let's say my friend has made an md5 hash of an email address and sent it to me. The email address will be something like 'jessica_XXXX@gmail.com', and I know it begins with 'jessica_' and ends with '@gmail.com'

Does software exist that would allow me to bruteforce the middle part, which is only four unknown characters?


texts: Anonymous key exchange protocol not secure vs. computationally unbounded adversary

texts: Explain why an anonymous key exchange protocol cannot be secure against a computationally unbounded adversary.


texts:
How do I implement asymmetric key algorithm into wireless medium using NS 2.35?

For example: node $A$ is a sender and $B$ is a receiver. Now, $A$ is sending a packet using $B$s public key (encryption) and $B$ decrypts that packet using its private key .

My question is: how to produce the key into that wireless node and do the privacy stuff? Is it possible at all? If, are there any books or materials regarding this?


texts: Diffie Helman obtaining $g^y \bmod p$ from $g^{xy} \bmod p$ and $g^x \bmod p$

texts: This may seem like a strange question. Lets say I have $g^x \bmod p$ and $g^{xy} \bmod p$. How can I efficiently obtain $g^y \bmod p$? I assume I must use modular inverse but I don't know where.


texts:
I have read in many places that SRAM PUF is considered a weak PUF, since it generates a single response (based on the value of all RAM cells upon power-up).

Why can't I use just a limited number of bytes from the RAM space in order to create a CRP?
For example  if I have a 64kB RAM, I can divide it into 256 sections, each section 256B long, obtaining 256 CRP's? (Assuming that all the RAM cells are stable and can be used for PUF...)


texts: Serpent Cipher 128bits (Example rounds on any plaintext/key)

texts: Is there are any possibility to see trace(example) of Serpent Encryption/Decryption on concrete plaintext/key example, (not code implementation) or at least animation of steps. During reading of Serpent I found article on IDEA Encryption with full round description on concrete plaintext https://ru.wikipedia.org/wiki/IDEA which explains how roundkey forms, encryption/decryption goes which is enough to start implementation and verify solution. But there are nothing likely about Serpent, only description of S-Box/IP constants but nowhere about brief plaintext example like in previous IDEA on Wikipedia. So it's nearly impossible to understand how Serpent encrypts and decrypts plaintext. Also there is an in-depth step description of AES http://www.formaestudio.com/rijndaelinspector/archivos/Rijndael_Animation_v4_eng.swf Where is it possible to see on a same examples but for Serpent? The only thing is available is test vectors but it is not a rounds description like in articles above. Thanks!


texts: Relation between decisional SIS and leftover hash lemma in lattices

texts:
The semantic security of Regev's cryptosystem [Reg05] is based on the LWE assumption and leftover hash lemma. This lemma implies that because $m \approx (n+1)\log q$ is large enough, so for uniform $A\in \mathbb{Z}_q^{(n+1)\times m}$ and uniformly random $x \in \{0,1 \}^m$, the term $Ax\in \mathbb{Z}_q^{n+1}$ is close to uniform.

Now, I'm a little confused. I see no difference between this lemma and the hardness of decisional SIS problem. I think the condition on $m$ is also for being able to guarantee the existence of a solution for the corresponding SIS problem (and so having the right version of this problem).

Can someone explain this?


texts: Difference between Asmuth-Bloom and Shamir's Secret Sharing

texts:
Both Asmuth and Shamir are threshold based secret sharing schemes and perfectly secure.

In which point of view  Asmuth bloom secret sharing scheme is better than Shamir secret sharing scheme.

Could you please give me anyone reason Asmuth bloom secret sharing scheme is better than Shamir secret sharing scheme.


texts: Prove that a signature scheme is RUF-NMA and not EUF-CMA

texts:
I am working on the following exercise:

Now, assume the following signature scheme:
$\operatorname{KeyGen} (1^k$) : On input of a security parameter $k$, choose a symmetric bilinear group with $e : G \times G \rightarrow G_T$ where the common group order of $G$ and $G_T$ is a prime of bitlength $k$. Further, let $g$ generate $G$. Choose $\mathit{sk}$ randomly from $Z_p$ and $\mathit{pk} \leftarrow  g^{\mathit{sk}}$ and return $(\mathit{sk}; \mathit{pk})$.
$\operatorname{Sign} (\mathit{sk};m)$ : On input of a secret key $\mathit{sk}$ and a message $m$, output a signature $\sigma \leftarrow  m^{sk}$.
$\operatorname{Verify} (\mathit{pk}; m; \sigma)$ : On input of a public key $\mathit{pk}$, a message $m$ and a signature $\sigma$, return $1$ if the following holds and $0$ otherwise:
$$e(m; \mathit{pk}) = e(\sigma; g)$$

I showed that the scheme works correctly. Now I need to show that the scheme is

random message unforgeable under no message attacks (RUF-NMA)
is not existentially unforgeable under chosen message attacks (EUF-CNMA)

Concerning point 1) I think that being able to guess the signature for a given message $m$ and a given public key $\mathit{pk}$ would violate the computational Diffie Hellmann assumption in symmetric bilinear groups (CDHSBG). But how could I write that down more formally?
Concerning 2) I suppose I have to find a suiting example for such an attack, but I am struggeling to find one.
Could you help me?


texts: What is the hardness in Decisional Linear Assumption (DLIN)?

texts:
I had understood what does the DLIN assumption means and here is a related question. But I fail to understand the 'real hardness' in this problem.

I would be grateful if someone can help me to understand this.


texts: Is MAC process different for symmetric and asymmetric?

texts: Message Authentication Code as far as I know works on the shared secret key. Do they work in the same way. Is there no difference between symmetric and asymmetric processes. Can anyone please explain me from message integrity and authentication perspective?


texts: How to implement a Cryptographic Pseudo Random Function

texts:
I need three pseudo random functions which all take  a
seed S (t-bits long).

The functions should map from

$d$ bits to $d$ bits
$d$ bits to $1$ bit
$d$ bits to $t$ bits

$d$ is $10$ bits
$t$ is $2048$ bits

Can you link me to some c++ implementation(or any language) or tell me how to implement it?


texts: TLS client authentication from static client image

texts:
I'm trying to implement mutual authentication for a TLS connection between a server (ONOS OpenFlow controller) and multiple clients (OpenFlow switches). I'm restricted in that I must create a single firmware image that will be pushed to the switches and the switches must not be manually configured after that.

Traditionally, one would set up a central authority and once the client created it's key pair the CA would sign it. As far as I understand, this is not possible with the restrictions because the signing process needs to be done manually.

Authentication of the server on the clients should not be a problem because the servers public key can be included in the firmware image.

Is it possible to achieve client authentication with these restrictions?
Would it be an acceptable solution to distribute one single key pair to all clients in the firmware image?

Reference: OpenFlow specification - https://www.opennetworking.org/wp-content/uploads/2014/10/openflow-switch-v1.5.1.pdf#subsubsection.6.3.6


texts:
I am implementing some of the algorithms in RFC 7518 and I noticed that AES_CBC_HMAC_SHA2 contains the following paragraph:

  The secondary keys MAC_KEY and ENC_KEY are generated from the
     input key K as follows.  Each of these two keys is an octet
     string.

  MAC_KEY consists of the initial MAC_KEY_LEN octets of K, in order.
  ENC_KEY consists of the final ENC_KEY_LEN octets of K, in order.

  The number of octets in the input key K MUST be the sum of
     MAC_KEY_LEN and ENC_KEY_LEN.  The values of these parameters are
     specified by the Authenticated Encryption algorithms in Sections
     5.2.3 through 5.2.5.  Note that the MAC key comes before the
     encryption key in the input key K; this is in the opposite order
     of the algorithm names in the identifier "AES_CBC_HMAC_SHA2".

Why would the encryption key be different than the MAC key? The examples I see in wikipedia show that the same key is used for both.

My understanding is that because in JWE only the message is authenticated, it means that the key is available for tempering and since the MAC key and the MAC are in a known location, it should be possible to forge messages.

Am I incorrect in that assumption? Why did the RFC authors chose to split the keys instead of reusing it?


texts: Where to store public key of an asymmetric cryptosystem?

texts:
I am developing an application that uses ECIES encryption and I am currently storing private keys in secure place on each peer and storing public keys in a shared database (accessible by all peers). Is this a problem?

Logically knowing a public key of some peer allows me to send him a message, and no risk because the private key is unknown. Can someone explain to me whether this approach is secure?


texts: Identify the cryptosystem where $\ m = c^2 \bmod n$?

texts:
I came across with cryptosystem whose decryption method is: $\ m = c^2 \bmod n $. It's exact opposite of Rabin's, where's the same formula is used for encryption.

What is the name of this cryptosystem?
How does the encryption function in this system work?


texts: Decrypting Multi-Prime RSA with e, N, and factors of N given

texts: I was wondering if there was any way to compute the private key $d$ when knowing only $e$ and $N$, and being able to factor $N$ as 4 prime numbers $p, q, r$ and $s$. I've been searching for days and I can't find any way.


texts: Relation between k-th shortest vector of a lattice and (n-k+1)-th shortest of its dual

texts:
Let $\Lambda$ be an $n$-dimensional lattice and $\Lambda^*$ be its dual lattice.

For any $k \in \{1, 2, ..., n\}$, let $\lambda_k(\Lambda)$ be the $k$-th successive minima of $\Lambda$ (analogously for $\lambda_k(\Lambda^*)$).

How can we prove that $\lambda_k(\Lambda) \cdot \lambda_{n-k+1}(\Lambda^*) \ge 1$ ?

That comes from the following exercise of a Micciancio's course from 2014:

  Prove that for any $n$-dimensional lattice $\Lambda$, $\lambda_1(\Lambda)\cdot \lambda_{n}(\Lambda^*) \ge 1$. More generally, prove  that  for  any $k$, $\lambda_k(\Lambda) \cdot \lambda_{n-k+1}(\Lambda^*) \ge 1$. [Hint:  For the first part, consider the scalar products between a shortest lattice vector and
  $n$ short linearly independent vectors from the dual lattice.]

Using the hint, I could solve the first part like this:

Take $v \in \Lambda$ and $x_i \in \Lambda^*$ such that $||v|| = \lambda_1(\Lambda)$ and $||x_i|| = \lambda_i(\Lambda^*)$ for $1 \le i \le n$.

Observe that $\langle v, x_i \rangle \in \mathbb{Z}- \{0\}$ for some $i$, because $\langle v, x_i \rangle$ must be different from zero for some $i$ (otherwise, we would have $n+1$ orthogonal vectors in an $n$-dimensional space) and $\langle v, x_i \rangle$ is integer by definition of dual lattice.

So, $1 \le |\langle v, x_i \rangle| \le ||v|| \cdot ||x_i|| \le \lambda_1(\Lambda)\cdot \lambda_i(\Lambda^*) \le \lambda_1(\Lambda)\cdot \lambda_n(\Lambda^*)$.

But how to generalize that argument for any $k$?


texts:
As I understand, PUFs work by using two procedures: generation and reproduction. Generation reads a value $w$ from a fuzzy source and generates a key $R$ and helper data $P$. Then, in the reproduction procedure, it reads $w'$ from the fuzzy source and, using $P$, is able to recover $R$.

My question is: this seems to assume that $P$ can be stored safely and can be authenticated, since if a attacker changes the value $P$ that is stored then he can force the system to use a different key. How can this be done, if you don't have a key in the first place? Or am I missing something?

(I have followed the notation from A Soft Decision Helper Data Algorithm
for SRAM PUFs by Maes, Tuyls and Verbauwhede.)


texts:
Say you have an integer that is produced by multiplying two random numbers

$$x_1 = a \cdot b_1 \bmod(p-1)$$ where $a$ and $b_1$ are relatively prime to $p-1$ and $p$ being a large prime.

Knowing $x_1$ leaves you with $p-1$ pairs of numbers for $a$ and $b_1$, so guessing the correct factorization is hard (right?).

Do you get any advantage in finding the correct pair if you get more $x_i$ where one of the factors is re-used? E.g.:
$$x_2 = a \cdot b_2 \bmod(p-1)$$


texts: If a new hash function were made that simply truncated sha-256 to the first N bits, how much insight would it provide into sha-256?

texts:
Clearly it would provide perfect insight if all 256 bits were used. What about if 255 were used? Would the general behavior and properties of "sha-255" be expected to be close to sha-256? What about "sha-5?" I imagine at some point the insight we can gain must break down, but am not sure exactly where that is.

sha-256 has such a large range of potential outputs that it is impossible for me to do certain experiments with it to analyze the behavior. But I presume that I couldn't, for example, truncate outputs to the first 10 bits or whatever, and then assume that observed behavior will extrapolate to the real sha-256, or else we would likely be able to know far more about it than we can.

I like to learn by experiment and observation. Are there any constructs with behaviors similar to cryptographic hash functions like this, but that I can actually exhaust the range of, and gain any insight into the secure constructs from?

My guess is no because of the lack of some insights into the secure constructs, but I'm not certain. Is insight already lost at "sha-255?"


texts: Getting 88bytes cipher output from 48bytes input in AES

texts:
The other day I saw this Hybrid Cryptographic Algorithm in the Google and felt curious about it. I am trying to understand this Hybrid Algorithm. And hopefully its not so hard to understand whats going on until AES portion comes up. Here in this research paper the author gives 48bytes input to AES and gets 88byte output from AES.

I hope the author won't mind that I copied a part of the image and gave it in here.

My question is, How is this possible? AES always gives cipher size that is divisible by 16. But 88byte is wired! Can anyone help me by explaining or giving a hint what might be the way to achieve this?

-Thanks.


texts: Why does the Node crypto library do Diffie Hellman this way?

texts:
I was sifting through the Node Crytpo library and I came across their Diffie Hellman utility class. Their class implements a generateKeys function that, in their words,

  Generates private and public Diffie-Hellman key values, and returns
  the public key in the specified encoding

My understanding of Diffie Hellman is that both parties only ever need to generate a single random number, not a public/private key. I suppose that you could call this random number a public key and that's what this function returns, but where does a private key come into this process?

I know that in Station to Station protocol a public/private key pair is used for signing. Is that what is happening here? Could this class be used for Station to Station protocol as is?


texts: Hash of multiset of values, which lets me compute the hash of the union

texts:
Cryptographic hash functions normally take as input a bitstring.

I am looking for a hash function that takes as input a finite multiset of values.  In other words, given $S \subset \{0,1\}^*$, I want to compute $H(S)$, a hash of $S$.  Also, I would like this function to be chosen so that given the hashes $H(S),H(T)$ of two multisets $S,T$, I can efficiently compute the hash $H(S \cup T)$ of their union.  (If you like, you can think of this as a sort of associativity property.)

I would prefer a hash function that behaves essentially like a random oracle on this domain.

Are there any good constructions?  Are there any constructions that are based upon a standard hash function and whose security is reducible to the security of the underlying hash?

Here is another way to think about it.  I want a hash function that accepts a sequence of bit-strings as input.  If the input is $x_1,\dots,x_m \in \{0,1\}^*$, I'll let $H(x_1,\dots,x_m)$ denote the output.  I want this function to have two properties:

Commutative: If $y_1,\dots,y_m$ is a re-ordering of $x_1,\dots,x_m$, then $H(x_1,\dots,x_m) = H(y_1,\dots,y_m)$.
Associative: Given $H(x_1,\dots,x_m)$ and $H(y_1,\dots,y_n)$, there is an efficient way to compute $H(x_1,\dots,x_m,y_1,\dots,y_n)$ (without knowing the underlying entries $x_1,\dots,x_m,y_1,\dots,y_n$).


texts: Average time for a brute force attack given 200 try per second

texts:
This is from an exam question.

  What is the average time to success at a brute force attack on a 56-bits key algorithm, if you're able to make 200 tries per seconds?

Let's suppose we got a crypted and decrypted version of a given text, so we know instantly if the attack is succesful or not.

The given answer to this question was 5700 years, but that's not what I found. Here's my reasonning :

There is 2^56 possible keys. We need to calculate average time, so we'll only need to try (2^56)/2 possibilities.

We have 200 tries per second, so we'll need (2^56)/(2*200) seconds to try them all. That's 1.8014399e+14 seconds

(1.8014399e+14)/(60*60*24*365) = 5712328.45003 years.

Where's my error?


texts: Where can I get the correct and precise algorithms for elliptic curve cryptography?

texts: I have been asked to implement cryptographic operations using elliptic curves. I would like to get precise algorithms for various processes like key generation, digital signature and verification. I found this link, but I just want confirmation on the algorithms provided there are correct or not. I would also like to know if there is any standard site for this topic whose information are authentic and can be trusted.


texts: Reconstruction vector in Linear secret sharing schemes

texts:
Suppose we have a policy $A \wedge ( D \vee (B \wedge C))$ with attributes ${\{A,B,C,D}\}$. The set of subsets of attributes which satisfy this policy is ${\{{\{A,D}\},{\{A,B,C}\},{\{A,B,D}\},{\{A,C,D}\}}\}$ of which ${\{{\{A,D}\},{\{A,B,C}\}}\}$ is the set of minimal subsets.

We convert the above boolean formula into a LSSS matrix $L = {\{{\{1,1,0}\},{\{0,-1,1}\},{\{0,0,-1}\},{\{0,-1,0}\}}\}$ according to this(Pg. No 30).

We usually find a vector $g$ such that $g^T \cdot L = (1,0,0)$ for all such authorized subsets such that $\forall i \in [4], (g_i = 0) \vee (g \in Attr)$.

If I understand it correctly, suppose a user has attributes $Attr ={\{A,D}\}$. That means his input vector in this case will be $V = (1,0,0,1)$. Since he does not have $B,C$ those $g_i$s (false attributes) will be assigned $0$ and then we solve the equation of unknowns $g = (x_1,0,0,x_2)$ to get $x_1 = 1$ and $x_2 = 1$.
So in this case, it turns out that $g = V$. Is this the right way to calculate $g$?

Assuming above way of calculating $g$ is correct, if he has $Attr ={\{A,B,D}\}$, then if we proceed with the same procedure as above ( the equation of unknowns will be $(x_1,x_2,0,x_3)$), how do we proceed to calculate $g$ as we then have two cases?. I know that ${\{A,B,D}\} \supset {\{A,D}\}$ as is the case for monotone policies.

Another way is that each subset of the rows of this matrix includes $\mathcal{e} = (1,0,0)$ in its span if and only if the corresponding attributes satisfy the formula. We take the rows corresponding to ${\{A,D}\}$ and find the coefficients $(1,1)$ so that $e$ is in the span. Then why do $\{A,B,D\}$ and $\{A,C,D\}$ have the same coefficients i.e (1,0,1)? I have a vague intuition but not sure.

What is the correct way to calculate $g$?


texts: Cryptographic pseudo-random generation of address subsets

texts:
Suppose I have devices which broadcast, on an insecure channel, 32-bit addresses.
I want to make these devices untraceable - one way to do so is to allocate for each device a distinct subset of address, for example $X=256$ addresses for each device with no repetitions, and make each device change its address from time to time (to a different number in its subset).
A secure receiver, who knows how the addresses-subsets are separated, could trace the origin device of the address.

However, this would require to store $X$ addresses on each device.

Another way is finding some injective function $f:Z_{2^{32}} \to Z_{2^{32}}$, where the first device will calculate on-the-fly the addresses $f(0), ..., f(X-1)$, the second device will calculate $f(X), ..., f(2X-1)$, etc...
However, if the code of this function falls to the wrong hands, the whole mechanism becomes worthless (I'm talking about physically breaking and reading the code secrets of one of the devices, not only reading its addresses from outside).

A third way is to have a different salt in each device and a CSPRNG executed $X$ times per device - leaving out salts that generate addresses that are "already taken" by previous devices.
In this case, after some time (around $2^{32}/X$ addresses, $2^{32}/{X^2}$ devices), it will become hard to find salts that do not generate "already taken" addresses.

Is there a mechanism that is both memory efficient and secure, i.e. breaking one device won't give too much information about the addresses of other devices (except that they are different from those of the broken device), without loosing too much of the address space (keep generating "devices" easily)?

Thanks

--- EDIT ---

Fourth way:
Similar to the third way, I can create create pairs of $(s_1, l_1), (s_2, l_2), ...$ where $s_i$ are randomly chosen salts and $0 < l_i \leq L$ is the number of times I can execute the CSPRNG on $s_i$ before getting a collision with an address generated by a previous $s_j$ (for $j < i$).

Then all I have to do is to give some $(s_i, l_i)$ pairs to each device so it could generate the amount of addresses I want.
For example, if every $l$ is a powers of 2, I could make devices that have pairs like:
$(s_{i_1}, 128), (s_{i_2}, 64), (s_{i_3}, 32), (s_{i_3}, 16), (s_{i_4}, 8), ...$,
and when I run out of $(s, 128)$ pairs, have devices that have:
$(s_{i_1}, 64), (s_{i_2}, 64), (s_{i_3}, 64), (s_{i_4}, 32), (s_{i_5}, 16), (s_{i_6}, 8), ...$

I am not sure about the average amount of memory I need on each device, but I know that the generated addresses can use much more than $1/256$ of the address space (suggested in the "third way"). Obviously, when it comes to pairs like $(s, 1)$ it would be more efficient to simply store the generated number...

I think there is a fundamental problem with what I'm trying to do. Informally, I am trying to allocate random numbers to each device and "compress" them. The only way to do that is to generate the numbers pseudo-randomly based on a secret, but then other devices must "know" that secret to prevent collisions - i.e. if a device is compromised then the secrets of other devices are lost too.
An asymmetric mechanism is needed - knowing that an address is taken by a different device without knowing the other device's secret. I don't believe it's possible with 32-bit numbers.


texts: Using 3DES decryption to get a specific result

texts:
I want to get 3DES to get a predictable result; assume I have:

key: [any]

data: [any]

then I want to apply 3DES decryption on key and data to get a specific result, such as:

decrypted 3DES: 12121212121212121212121212121212

Is this possible in theory?


texts: Are there key-derivation functions that are safe to use in parallel on the same secret?

texts:
I'm considering using a key-derivation scheme for generating multiple keys from the same user secret. It is important that given all but one of these derived keys, it is not feasible to calculate the last one. Tunable difficulty would be a big plus.

Is there such a function, or set of functions, that are safe to use in parallel on the same secret?

This is not a duplicate of this question because I do not have any way to store a client-side salt between different devices. Using a constant would work, since that can be stored in the source code, e.g. sha256(user_secret + "first_static_salt"), but I have no idea if such a scheme would be secure. I also don't have the same parameters and same key derivation function requirements of that question. Using three different functions would work fine for me.

EDIT:
I only have the user password for entropy. Any user-specific salt used would have to be stored on a server, which means that it would be known for all parties involved (unless you encrypt it with the user password...).

The goal here is to hide sensitive data from the servers; they only need metadata to function properly, so there's no reason to send sensitive data through them. The current setup would use two different keys, one for authenticating with the servers, and one for encrypting/decrypting the actual data. Most servers would just push around uuid's, and these uuid's would be used to access a separate system where the actual sensitive encrypted data is stored. The client would then interact with these two separate systems.


texts: Why are the lower 3 bits of curve25519/ed25519 secret keys cleared during creation?

texts:
I am currently experimenting with ed25519 and I noticed that on secret key creation, bit 254 is always set and the lower 3 bits are always cleared. I found that bit 254 is always set to protect against timing attacks in this question: When using Curve25519, why does the private key always have a fixed bit at 2^254?

But why are the lower 3 bits cleared. Obviously it has to do with the formula in the curve25519 paper:
The set of secret keys is defined to be $\{\underline{n} : n \in 2^{254} + 8\{0, 1, 2, 3,\ldots, 2^{251}-1\}\}$

It's because of the 8 in there, but why is that 8 there? I suspect it has something to do with theorem 2.1 in the curve25519 paper, but I am not sure, because I do not understand fully what is being proven there.

I am experimenting with ed25519 primitives in some cryptographic routines which need me to add scalars to the secret key (add secret keys). Even if I add two well formed ed25519 secret keys, the result will not always have bit 254 set and the lower 3 bits cleared. Is this a security problem? I understand the risk for bit 254 but not the lower 3.


texts: Linear Feedback Shift Registers analysis

texts: Cryptanalysis of Linear Feedback Shift Registers. From this site I found that lfsr could be break by Berlekamp-Massey algorithm. What is the specific progress of this algorithm? And if there is any other way to do it


texts: One Time Pad OTP : Optimal modular base per given plaintext space?

texts:
Background:  my question at :

My pencil and paper One Time Pad works fine without modular math ...... or does it?

I am trying to understand, from a layman's point of view, how to make the best one time pad scheme.

From responses to my above referenced question in another post, I understand now why I should use modular math in the scheme, and that the keyspace should be at least as large as the plaintext space.

So, moving beyond those points, I would like to try to understand the best modular base per given plaintext space.   For example:

My alphabet's plaintext space is 40 characters, numbered 0 through 39.

So, I am using mod40 math.   But I am only using mod40 math because I read elsewhere that my modular base should equal the size of my plaintext space.
But I also know that my OTP will still function if my mod base is less than the size of my plaintext space or more than that size.  So, in my example, I could use mod30 math or mod50 math just as well as mod40 math.

Therefore, my question is: what is the importance of the mod base in relation to the plaintext space, and, is there an optimal relationship between the two, and, if so, how can I know the optimal ratio of  "mod base/plaintext space" in any OTP system?


texts: How do you go about breaking a Quagmire III Cipher?

texts:
For example, take K1, from the Kryptos sculpture, which has been long solved. It's text is as follows:

EMUFPHZLRFAXYUSDJKZLDKRNSHGNFIVJ
YQTQUXQBQVYUVLLTREVJYQTMKYRDMFD

Now, I already know they keywords used (because the solutions are online) and they are PALIMPSEST and KRYPTOS. However, I do not understand how you would go about finding these keywords if you do not already know them.

Any help would be appreciated!


texts: Padding Oracle Attack CBC Mode: If the set of characters of plaintext is known, then can you speed up the process

texts:
Consider AES-256, 128-bit blocks, and PKCS#5 Padding.
During a Padding Oracle Attack, a manipulated byte of cipher text is sent to the oracle and we eventually hope to find out what that respective byte of plaintext was.
If I know the set of possible characters in the plaintext will only be lowercase english letters, then is there any way in which I can speed up the deciphering process? If so, then specifically what would this look like?


texts: Encryption of a number with RSA bigger than $n$

texts:
I'm having trouble understanding why encrypting a number $m$, which is larger than $n=p\cdot q$. I've looked into the following threads:
Why RSA can't handle numbers above 76?
Why does plain RSA not work with big messages ($m>n$)?

Can somebody point me to a simpler source, that explains this?


texts: Predicting Java's PRNG using partial output

texts:
I have a program (a game) that uses Java's nextInt function with parameter 0x10000 to get a random 16-bit number.
Java's nextInt() is an 48-bit seed LCG with the following formula:

seed[n+1] = (seed[n] * 0x5DEECE66DL + 0xB) mod (1 << 48)

nextInt() is implemented in such a way that the random number I receive is the current seed's most significant 16 bits when given argument 0x10000. [Java only does this for an argument that is a power of two]

So let me describe the situation: In the game, I get to have two sequential outputs of nextInt(0x10000), R[i] and R[i+1] (which are respectively seed[i] and seed[i+1]'s top 16 bits).

My question is: what information can I extrapolate about the next output of randInt() (R[i+2]) ?

EDIT: I'm in a situation in which a bruteforce of even more than 30,000 steps is not practical..and all I have are these two consecutive outputs. So, is it even feasible extracting some info given these restrictions? (And please be gentle, I don't have any knowledge in math beyond high school)


texts: relationship between share size and entropy in secret sharing

texts:
In an $(s,r,n)$-ramp scheme, we require that any
subset of at least $r$ parties can recover the secret, while any subset of size at most $s$ cannot learn anything about the secret.
In Bogdanov et al.'s paper, they prove that any $(s,r,n)$-ramp secret sharing scheme for a one-bit secret requires shares of at least $\log((r+1)/(r-s))$ bits.

My question. Does share size (e.g. $\log((r+1)/(r-s))$ bits) have anything to do with the entropy of information which each party holds? A naive approach (see here) shows that the sum of entropy of information assigned to each party should be greater than $\frac{n}{r-s}$ bits, when sharing a one-bit secret. Is this bound tight?


texts: What is the key generation and management process of a fully homomorphic encryption system?

texts:
I've been very interested in fully homomorphic encryption lately, and I understand the concept well enough, but there is one thing that I don't understand...
What is the key creation and, more particularly, how are keys distributed and managed in a fully homomorphic encryption system?
I've heard its like symmetric and asymmetric encryption, but that's kind of an apples and oranges thing in my mind.
So how are keys created and distributed, or managed, in a fully homomorphic encryption system?


texts:
Consider the ECDSA protocol, which is applied in different environments e.g. the Bitcoin system (for user addresses, and transaction signing).

What are the greatest threats in terms of algorithms that could solve the underlying discrete log problem for groups over elliptic curves? I found:

General Number Field Sieve
Pohlig-Hellman
Baby-Step-Giant-Step
Pollard's Rho

(excluding quantum algorithms)

to be the most efficient. Are all of them able to solve the ECDLP and if so, what is their complexity (runtime)?


texts: How hard is it to recover $p$ if I can get $h(p) \oplus h(p^*) \oplus r$ and $h(r)$?

texts:
Assume that $h:\{0,1\}^* \rightarrow \{0,1\}^\lambda$ is a cryptologic hash function, $r$ is taken randomly from $\{0,1\}^\lambda$, $p$ is a low-entropy password and $p^*$ is a guess. Now we get $h(p) \oplus h(p^*) \oplus r$ and $h(r)$ but don't know $h(p)$ or $h(p^*)$.

Then there are two problems is a problem:

Can we get $\Delta{}h = h(p) \oplus h(p^*)$ by a brute-force cracking? (Yes.)
Can we get $h(p)$ (and $p$, due to the low-entropy property)?

There may be a slight different problem to consider easily, what if we get $\mathsf{pad}(p) \oplus \mathsf{pad}(p^*) \oplus r$ and $h(r)$, where $\mathsf{pad} (x)$ simply pads x with zeros?


texts: is Authentication tag always appended at last to ciphertext in AES-GCM 256?

texts:
I am using AES GCM 256 to encrypt/decrypt a UUID string,We are using java 7 + bouncy castle library for this,We are getting authentication tag of 128 bit ,i am confused ,whether it's position is always at the last or not.

Ex:-

Plain text :- a7d80af9-6386-48ff-b9b6-71ad80257b34

IV :- PKBlbi3htx1PLdOx

Cipher Text : PKBlbi3htx1PLdOxMnEbJHN8DSP7wksgm86XWRCTU6a78drESnrnl30XteEqMy9/H/hD+7PGXTOyPz1rQjM0tA==


texts: Why does PSS produce an EM message that's almost as long as the modulus?

texts: I try to understand the reasons behind the design of PSS scheme for RSA. Why is the length of the EM message (that is, the result of PSS transformation just before signing) equals approximately to the size of the modulus? Why PSS does not use a last call to a hash function (for instance SHA-256) so as to reduce the size of the resulting element before performing the exponentiation?


texts:
While reading the Wiki page on RC4 I noticed that the key size must be in the range of 40–2,048 bits.

Why is that? Is there a reason it can't have a lower or higher length?


texts: How to find the co-efficients of a function within Zp[x]?

texts:
I am a newbie in Finite Field arithmetic and while trying to implement an Elliptic Curve Cryptography based ABE scheme in a programming language, I am unable to understand how to implement function fields.
I am given a function definition within a finite field of $p(i.e. Z_p[x])$ where $p$ is some large prime number. How do I find the co-efficient of $x^k$ in the expansion of $f(x)$?
Function definition:
$$f(x)=\prod_{i=1}^3 (x+H(i))^i$$
where, H(k) is a one-way hash function giving a large output.
Q1. Since the function is defined in $Z_p[x]$, should all the co-efficient be first calculated using elementary algebra and then taken modulus with $p$?
Q2. If we want to calculate the value of $f(\alpha)$, where $\alpha$ is some constant, can we do it using the final function polynomial of the previous step and substituting all x's with $\alpha$ and then taking a modulus $p$ again?


texts: How many possible Enigma machine settings?

texts:
I'm trying to calculate the amount of settings the enigma machine has. I have found several sites regarding this topic, but it seems like there are two answers to my question. The first answer is 158,962,555,217,826,360,000 and the second is 107,458,687,327,250,619,360,000. Where the difference is that in the second answer, it has been taken into account that the notched rings on the enigma could be set as well, giving 26 * 26 = 676 more settings than the first answer.

But which answer is the right one, and why? How many possible different Enigma machine settings are there and how can one determine this number?


texts: One-one correspondance complete function

texts:
I am reading the paper by John B. Kam and Georges I. Davida (1979) titled Structured Design of Substitution-Permutation Encryption Networks.

On page 749 it reads the following:
Definition: Given a one-one corespondence: f:{0,1}n   --> f:{0,1}n, f is said to be complete if, for every i,j belongs {1, ..., n}, there exist two n-bit vectors X1 and X2 such that X1 and X2 differ only in the ith bit and f(X1) differs from f(X2) at least in the jth bit.

My questions are:

What is meant by vectors here? (Can someone explain it using less math if possible?)
Can someone explain this, proably with a nice and easy example?
In general, what is the idea behind this?

If this is the wrong place to ask the question, please let me know so that I take this to the write place instead of voting negative or closing the question.


texts: Key Check Value standard practice for asymmetric cryptography?

texts:
I'm looking for a standard, or sound industry practice, for the equivalent of a Key Check Value, applied to the private key of a public key algorithm, like ECDSA.

For DES or 3DES keys, practice (as worded e.g. in EMV Card Personalization Specification) is:

  6.1.5 Key Check Value
  Purpose: The data is used to prove that a card/processor has access to a
  specific DES key value.
  Format: Binary, 3 bytes
  Contents: The three leftmost bytes of the result of encrypting eight bytes of zeros by the DES key concerned.

Notice that the above definition is slightly wrong: the KCV as defined does not prove anything beyond knowledge of the KCV. The actual purpose (and the one I'm interested about) is to guard against a wrong value of the key, either accidental, or deliberate from one participant in a scheme where the key is rebuilt from shared secrets (for simplicity, assume that's by XOR of the components, and that at least one participant does not cheat).


texts: AES file encryption with PBKDF2. Safe parameters?

texts:
I'm developing an application that will use public key authentication to contact some webservice. So the user has his keypair on his computer, and I want that file to be encrypted using AES with a key derived from a user's password.

I'm wondering if I'm using relatively "safe" parameters and way of writing the file.

Here are the PBKDF2 and AES parameters:

PBKDF2 Iterations : 1024
PBKDF2 Hash function : SHA256
PBFDF2 Salt size : 256 bits
PBKDF2 Derived key size : 256 bits
AES Cipher mode : CFB

Here is how the file is written:

Salt (Hex encoded)
Return line
IV (Hex encoded)
Return line
Encrypted file content (Hex encoded, encrypted using AES in CFB mode and the key derived from the user's password)

Maybe what's missing here is a HMAC (with SHA256, for example) to "guarantee" that the file hasn't been tampered with. Here's how probably I'd append it to the file, after "Encrypted file content":

Return line
HMAC-SHA256 with the content's encryption key

Thanks in advance.


texts: To avoid the dummy padding block, CMAC uses 2 separate keys K1 & K2. If padding is required, the final block is padded & then XORed with K1. If no padding is required, then it's XORed with K2. I understand how this avoids the extension attack. However, at the verification side, how does Bob know whether the final block was XORed with K1 or K2?


texts: Are there better alternatives to CRC32 for distributed download components hash calculation?

texts:
Given a server with with download resume capabilities (byte range), we can download a file chunk by chunk. Multiple people will download different parts of the file.

If a file A.jpg has blocks 1, 2, 3, 4, 5, 6.

Following are the people who obtained the blocks

Alice - 1, 2
Bob - 3, 6
John - 4, 5

What kind of hashing algorithm can be used to calculate the hash of A.jpg given that Alice, Bob and John can only hash each block separately?

Assume that the hashes for each block are located in a place Alice, Bob and John can access. And they can combine them as they wish.

What I've found: Combine two sha512 hashes to a single hash cannot be used.

I also found that CRC32 can be used, Are there any more algorithm ?

Desired outcome

Everyone should be able to generate the same final hash, which should be more powerful than CRC32 to prevent collisions. In the end I want to join the blocks to get the final file. So that Alice, Bob and John have the same file.


texts: can we use two different hash functions in single hmac?

texts: Can we use two different hash functions in single hmac..for ex' for inner layer hash function md5 and for outer layer hash function sha1


texts:
I have for a while used Koblitz curve (sect571k1), in ECDH and ECDSA. But I have started wonder if it is the most secure. I prefer security over efficiency. So the curve doesn't have to be the most efficiency curve.

I'm not looking for a curve that is only secure today, and the next few years. The compute power increases rapidly today, and I'm looking for a curve that is secure as far as possible in the future. So if someone is able to steal my encrypted data today, they should not be able to crack it in next 20 years, hopefully longer.


texts: How does authentication work for SSH login with a public key?

texts:
For SSH public key authentication in Cisco IOS it is sufficient to add RSA public key hash instead of content of that public key.

For example:

ip ssh pubkey-chain
  username admin
  key-hash ssh-rsa 539197BB0F11CE77A123334A97859E30 admin@server

From cryptography point of view, how does authentication actually work in such a case – public key hash on one side with corresponding private key on another?

I thought that we have to have a pair of keys exactly. Not a public key's hash on one side and a private key on another.


texts: Homomorphic encryption scheme for modulo reduction

texts:
I want to know if there is any Homomorphic encryption scheme that supports modulo reduction, i.e.,
using $Enc_{pk}(m)$ and a public $w$ to compute $Enc_{pk}(m \mod w)$.
Thank you.


texts:
This is a question I had in my exam today, and I'll be glad if someone can help me to find the answer.

A student built an encryption algorithm (something between DES and 3DES), in which the encryption is based on 2 keys, $K_1$ and $K_2$, and calculated this way:

$$Cipher = E_{K_1} (E_{K_2} (plaintext))$$

where $E_{K_i}$ is encryption using the key $K_i$.

An attacker knows:

A single plaintext.
The ciphertext of that plaintext.
The encryption algorithm.
Each key is 56-bit.

How can he find the 2 keys?

Of course there's the brute-force solution, looking in all the possible pairs of keys until we find the correct one.

My question is: Can we find another way, better than the brute-force, in order to find the keys?


texts: Is it generally considered desirable - or not? - to use an algorithm which encrypts a single byte into a byte array of length around 5 or 10?  Greater length allows me to add additional layers of obfuscation, but I don't know whether this is considered the sign of a naive amateur (which I am).


texts: What is the correct test/s to do in asymmetric algorithms to test their security?

texts:
I would do some test for evaluating security in asymmetric algorithms such as RSA and ElGamal to evaluate which of both are safer.

The basic problem is that I need to test the security of some symmetric and asymmetric algorithms to evaluate their security and to know which algorithm is more secure and his strength against real-time attacks. In both type of algorithms I have made a table with their vulnerabilities, but I want to test their security with some specific test. Then, I need a test that allows me to conclude that algorithm is safer, for both symmetric and asymmetric algorithms.

For instance, in symmetric algorithms the test that you can use is the avalanche effect link, but in asymmetric algorithms I have not found anyone and I only know that the avalanche effect is not for this type of cryptography.

Any suggestions on the possible test?


texts:
What is the more desirable for a block cipher's sub-keys ?

Given two blocks ciphers, letting all other properties be equal (they have the same strength), the only difference between them is that:

one generates a unique set of sub-keys for each key,
while the other generates a set of of pseudo random subkeys.

In other words for each different possible key, the fist cipher always generates a unique subkey set that only that key can, while the second has the possibility (however small) that it could generate a subkey set that another key might also generate.

Focus on this property itself:  assume everything else about the cipher and key derivation process are of sufficiently high quality.


texts: RNG and Mersenne twister learning resources for the amateur

texts:
I am a complete amateur in the area of random number generators. I would appreciate resources to begin learning.
Also I would also like to learn about Mersenne twister. Resources that are easy on the math side of these things would be more appreciated.
N.B: I have some programming experiences. I code in Python and JavaScript


texts: What are monotonic and non monotonic access structures in ABE ?

texts:
While reading Attribute Based Encryption Schemes, I did not quite understand what a monotonic access structure or non monotonic access structures are.

Is there a popular explanation of those terms ? any references ?


texts: Why are singular "elliptic" curves bad for crypto?

texts:
Consider the algebraic curve given by a short Weierstraß equation $y^2=x^3+ax+b$.

If $4a^3+27b^2=0$, then there are repeated roots of the right-hand side $x^3+ax+b$. How are these repeated roots bad for a discrete-logarithm-based cryptosystem?


texts:
I am trying to achieve the following:

Encrypted files are stored on users filesystem. The user uses my client to authenticate against a server. Once he is authenticated successfully he gets a token to decrypt the files.

Things I want to ensure: the user should not be able to cache the token for later use. like a one time token, so that he is no longer able to decrypt the files in some time in the future.

The client and server do only exist in my head, so anything that is possible can be applied to it. I am looking for algorithms/protocols to achieve my requirement.


texts: Can one tell private key entropy from a public key?

texts:
Given a weak entropy private key and its associated public key. Can we predict low entropy from the private key by examining the public key?
In other words, is the low entropy from the private key in some ways 'reflected'
in the public key?
What signals a public key can give in case of a weak private key?


texts: Advice for a high schooler intending to read about post-quantum crptography

texts:
I'm a high schooler who is interested in learning about post-quantum cryptography.

I would like to read some papers of post-quantum public key algorithms, shortlisted by NIST: https://csrc.nist.gov/projects/post-quantum-cryptography/round-2-submissions.

I have a basic understanding of abstract algebra, number theory, etc. I'm more than willing to learn more mathematical topics as necessary in order to understand the mechanics behind the algorithms I read.

Which paper(s) from the 17 shortlisted post-quantum public key algorithms would members of the Cryptography Stack Exchange Community consider the most accessible for a post-quantum newbie?

The overall aim of my personal project is to implement the algorithm on Python (that's the only language I know), then test it against a quantum computer stimulator.

I'd really appreciate the community's thoughts on the feasibility of my undertaking.


texts: Prove Vigenere cipher isn't perfectly secret

texts:
As part of a homework assignment I have to prove/disprove that a Vigenère Cipher with a key of length n, uniformly distributed in the alphabet, on a plain text of length 2n, also uniformly distributed in the alphabet, is perfectly secret.

The only theorem we have seen so far concerning perfect secrecy uses entropy:
if the plain text and the cipher text are statistically independent (H(PlainText) = H(PlainText | Ciphertext)), the encryption is perfectly secret.
Computing H(PlainText) is quite straightforward given the text is uniformly distributed on an alphabet of 26 elements.

But I don't know how to compute the conditional entropy of the plain text given the ciphertext to prove that these two aren't equal (I understand that this type of encryption isn't perfectly secret, mainly because the key is of length n and not 2n).

What is the way to approach this?


texts: Do we still need HMAC now that SHA3 is here?

texts:
In Another look at HMAC from Koblitz and Menezes, they state that HMAC came along because doing h(secret || message) was vulnerable to length extension attacks. But as far as I know, these kind of attacks only exist because of the Merkle-Damgard construction.

Now that we have SHA-3, that does not use such a construction, and that is not vulnerable to length extension attacks. Do we need to use the complicated HMAC-SHA3 or can we just use SHA3 as a MAC?


texts: Collision in Merkle–Damgård without a collision in compression function

texts: Is it possible to find a collision in Merkle–Damgård  just by omitting the extra one bit that is appended to each input without having a collision in compression function?


texts: Why is a hash of blocks - with index - weaker than hashing the entire thing?

texts:
Let's say we want to sign message $M$ with RSA using a safe hash function.
However, instead of signing $\operatorname{hash}(M)$,
We split the message into 64-bit blocks (|| is concatenation):

$$M = {m_0}||{m_1}||{m_2}||{m_3}\,...$$

For each block we calculate:

$${h_i} = \operatorname{hash}({m_i}||i)$$

and then we calculate the total hash:

$$h = {h_1} \oplus {h_2} \oplus {h_3}\,...$$

and sign $h$ with RSA instead of $\operatorname{hash}(M)$.

Why is it weaker than signing $\operatorname{hash}(M)$?

I know that the order of the blocks cannot be modified because of the concatenation of $i$, and that I cannot add the same block twice because of that too.

I think the answer involves collision, birthday or brute-force attack which may be faster than performing those attacks against $\operatorname{hash}(M)$ but couldn't show that. Any ideas?

P.S: Homework question - hint is enough :)


texts: Are there Guaranteed Proof-of-work Systems?

texts:
Proof-of-Work systems such as hashcash, it seems to me, do not actually prove that a certain amount of work has been performed. For example, in the case of hashcan, could not the first random hash choice just get lucky? Thus almost no actual "work" was performed?

My question is on the existence (and practicality) of methods that guarantee, within a probability, that a given minimum amount of "work" has been performed in each and every case, without compromising the average or maximum amounts.

On hashcash then, the probability of failing to prove work is the chance of "getting lucky". So, with a 20 bit zero hash target, that's around a few in a million (the first few random attempts out of a 2^20 space). Therefore a few in a million hashcans won't really be doing any work. But if i wanted to reduce this proof-of-work fail to a lower probability, simply increasing the zero bit space does not work, since it also drastically increases the average work.

To compare this to, say, the workload of compressing a file (eg zip). That's a much more controllable amount of work, roughly proportional to the input length.

Say we manufacture an unpredictable text generator, fed into zip, fed into a hash function. The proof of work is the generator seed and the final hash value. the generator output length controls the amount of work and saying you could "guess" the final hash is virtually impossible (compared to say 1:2^20).

But this example is not practical because it is symmetric, requiring the same work to be performed for verification.

so, are there any guaranteed (within probability) asymmetric proof-of-work systems?


texts: What do the inputs of `hash_df` look like?

texts:
I am making an implementation of hash_df (NIST documentation found in SP800-90A.pdf on page 67)

I found “Does hash_df use binary or an ASCII hexadecimal representation for numbers to be passed to the hash function?” which explained a few things, but im still not completely sure that I have it right. I am having trouble with part 4.1 under Hash_df Process as seen below

temp = temp || Hash (counter || no_of_bits_to_return || input_string)

Counter is expected to be a 1 byte binary value
no_of_bits_to_return is a 4 byte big-endian binary value
input_string is the concatenation of entropy_input, nonce and personalization_string.

so as an example if counter = 2, no_of_bits_to_return = 16 and input_string = "8581f93h" the later part of the function would look like this: (|| is concatenation. The no_of_bits_to_return binary value in my example could be incorrect. I need to get more familiar with big-endian  I just put this one in a converter)

hash(00000010 || 16000000 || 0011100000110101001110000011000101100110 001110010011001101101000)

Is this correct as per the NIST SP 800-90A documentation? I can’t find the documentation to confirm my assumptions and I am afraid I am horribly wrong.


texts: Is it safe to use a deterministic salt as an input to KDF (Argon2)?

texts:
I'm prototyping an app that uses client-side password hashing in order to hide the "real" account password from a server (the server hashes any recieved password anyway, so no plaintext records in the database). It seem to be a controversial thing to do but I didn't find any convincing arguments against it (I'm new to cryptography so please correct me if I'm wrong).

I'm trying to figure out what would be an appropriate salt for Argon2i. Many implementations generate random salt by default but it won't allow users to log in again because using new salt produces new hash. That's why I can't avoid using deterministic salt.

My understanding is: each salt value is better to be globally unique for each user so it seems like an email address could make an OK salt in a sense that it's unique, but not globally. Email + password would certainly lower the chances of a collision but some users might have the same passwords in many apps. I'm thinking about sha256(app name + email). Would it make a good salt?

My main question is about the implications of using a deterministic salt in general. Does it make the resulting hashes easier to crack? And if it's OK, what would be an appropriate way to generate such a salt?

Another related thing I'm wondering about is how easy is it to crack the hash and not the password itself? Let's say I use Argon2 to hash a password and use the same exact password as hash (argon2(pwd = "foobar", salt = sha256("foobar")). Would it help an attacker to reveal that password by any method except using a rainbow table?


texts: How to properly sign and verify using DSA? Can anyone spot my mistake?

texts:
The question that I am trying to answer is as follows:

10.14. The parameters of DSA are given by p = 59,q = 29,α = 3, and Bob’s private key is d = 23. Show the process of signing (Bob) and verification (Alice) for following hash values h(x) and ephemeral keys kE:

h(x) = 17,kE = 25
h(x) = 2,kE = 13
h(x) = 21,kE = 8

I managed to figure out part 1 correctly and then modeled the other two parts after part 1, but the problem is that both part 2 and part 3 came out to be invalid in the verification stage, and I am pretty sure that they were supposed to be valid. Here is my work:

h(x) = 17,kE = 25

Generation(Bob):

Chooses values p=59, q=29, α=3, d=23
Computes β = αd = 323 mod 59= 45 mod 59
sends (p, q, α, β)= (59, 29, 3, 45)
Actual signature generation:
compute hash message of h(x)= 17
1. choose enphemeral key kE = 25
2. r=(α^kE mod p) = 3^25 mod 59 = 51 mod 59
3. s= (h(x)+d*r)*α= (17+23*51)*3= 3,570 mod 59= 30 mod 59

sends (x,(r,s))= (x,(51, 30))

Verification(Alice):

1. w= r^(-1) mod q = 51^(-1) mod 29= 22^(-1) mod 29 ← solve using EEA (Euler’s Extended Algorithm)
    29= 22(1)+7
    22= 7(3)+1
    -----------
    1= 22+ 7(-3)            //Set equal to 1
      = 22+ (29+22(-1))(-3) //Substitute
      =29(-3)+ 22(4)        //Distribute
     22^(-1) mod 29 = 4 mod 29
2. u1= w*h(x) mod q = 4*17 = 68 mod 29 = 10 mod 29
3. u2= w*r mod q = 4*51= 204 mod 29= 1 mod 29
4. v = (α^(u1) * β^(u2) mod p)mod q
    = (3^(10)*45^(1)) mod 59) mod 29
    = (59,049*45 mod 59)mod 29
    =(2,657,205 mod 59)mod 29
    =  22 mod 29
5. v=22,
r mod q= 51 mod 29 = 22 mod 29
v = r mod q → Valid signature

h(x) = 2,kE = 13

Generation(Bob):

Chooses values p=59, q=29, α=3. d=23
Computes β = αd = 323 mod 59= 45 mod 59
sends (p, q, α, β)= (59, 29, 3, 45)

Actual signature generation
compute hash message of h(x)= 2
1. choose enphemeral key kE = 13
2. r=(α^(kE) mod p) = 3^(13) mod 59 = 1,594,323 mod 59 = 25 mod 59
3. s= (h(x)+d*r)*α= (2+23*25)*3= 1,731 mod 59= 20 mod 59
sends (x,(r,s))= (x,(25, 20))

Verification(Alice):

1. w= r^(-1) mod q = 25^(-1) mod 29 ← solve using EEA (Euler’s Extended Algorithm)
    29= 25(1)+4
    25= 4(6)+1
    --------------------
    1= 25+ 4(-6)             //Set equal to 1
      = 25+ (29+25(-1))(-6)  //Substitute
      =29(-6)+ 25(7)         //Distribute
     25^(-1) mod 29 = 7 mod 29
2. u1= w*h(x) mod q = 7*2 = 14 mod 29
3. u2= w*r mod q = 7*25= 175 mod 29= 1 mod 29
4. v = (α^(u1) * β^(u2) mod p)mod q
    = (3^(14)*45^(1) mod 59) mod 29
    = (4,782,969*45 mod 59)mod 29
    =(215,233,605 mod 59)mod 29
    =  12 mod 29
5. v=12, r mod q= 25 mod 29
v ≠ r mod q → Invalid signature

h(x) = 21,kE = 8

Generation(Bob):

Chooses values p=59, q=29, α=3. d=23
Computes β = αd = 323 mod 59= 45 mod 59
sends (p, q, α, β)= (59, 29, 3, 45)

Actual signature generation
compute hash message of h(x)= 21
1. choose enphemeral key kE = 8
2. r=(α^(kE) mod p) = 3^(8) mod 59 = 6,561 mod 59 = 12 mod 59
3. s= (h(x)+d*r)*α= (21+23*12)*3= 891 mod 59= 6 mod 59
sends (x,(r,s))= (x,(12, 6))

Verification(Alice):

1. w= r-1 mod q = 12^(-1) mod 29 ← solve using EEA (Euler’s Extended Algorithm)
    29= 12(2)+5
    12= 5(2)+2
    5= 2(2)+1
    ------------------
    1= 5+2(-2)                  //Set equal to 1
      = 5+(12+5(-2))(-2)        //Substitute
      =12(-2)+ 5(5)             //Distribute
      = 12(-2)+(29+12(-2))(5)   //Substitute
      =29(5)+ 12(-12)           //Distribute
     12^(-1) mod 29 =-12 mod 29
    w= 17 mod 29
2. u1= w*h(x) mod q = 17*21 = 357 mod 29= 9 mod 29
3. u2= w*r mod q = 17*12= 204 mod 29= 1 mod 29
4. v = (α^(u1) * β^(u2) mod p)mod q
    = (3^(9)*45^(1) mod 59) mod 29
    = (19,683*45 mod 59)mod 29
    =(885,735 mod 59)mod 29
    =  27 mod 29
5. v=27, r mod q= 12 mod 29
v ≠ r mod q → Invalid signature

I have no idea what I did wrong. I checked my answers several times, so if someone could point out the mistake that I made that I cannot see, I would appreciate it!


texts:
I am a beginner to homomorphic encryption scheme.
As far as I think, it is just a kind of concealing real value without using standard encryption algorithms such as AES,DES or RSA.
For example , for concealing value of $3$, it expresses $6$ where ($6=2 \times 3$).
Decryption is done successfully if user knows $2$ (secret value).
Is it correct or not?


texts: Doubt about published test vectors for gimli hash

texts:
In https://eprint.iacr.org/2017/630.pdf and https://gimli.cr.yp.to/gimli-20170627.pdf there are test vectors for the gimli hash function. I have compile the reference C code test_hash.c from https://gimli.cr.yp.to/gimli-20170627.tar.gz on two systems (Intel x86/Win, ARMV7l GNU/Linux) and consistently get results that differ from the printed vectors. The paper lists e.g.

input: "" (empty string)
input (bytes): (0 bytes)
output:
bd2a1b1cdab81f9fea9d5fd513372ab9d1481428385de2b2d3571d8504fdd703

but both executables give

b0634b2c0b082aedc5c0a2fe4ee3adcfc989ec05de6f00addb04b3aaac271f67

  Has anybody verified the test vectors from the papers?

For the permutation/compression function test program test.c my results are the same as given in the file test.exp.


texts:
A weak key for DES is a key $K$ such that $DES_{k_1}(DES_{k_2}(x))=x$ for all $x$.

I don't get why are the 4 keys $k_1||k_2$: $1^{112}$, $0^{112}$, $0^{56}||1^{56}$, $1^{56}||0^{56}$ considered as weak. (Also didn't find some detailed explanation in the web.)


texts: Can an RSA public key be generated without ever knowing the factors?

texts:
Context: http://blog.cryptographyengineering.com/2013/12/a-few-more-notes-on-nsa-random-number.html

Assume I wanted to use RSA as the basis for a hash function or DRBG. Also assume that my construct would be insecure if someone were to have the private key. Is there any way generate the a usable public key to be used such that it is provably just as hard for me to generate the private key as it would be for anyone to do so?

I'm willing to take for granted:

the existence of a suitable source of nothing-up-my-sleeve numbers
the availability of significant computational resources.

The best idea I've come up with would depend on the ability to prove a lower bound the the size of the smallest factor in a number (e.g.: an $N$-bit number where all factors are at least of size $N*0.49$-bits) with significantly less work than it takes to actually factor it. (That and the ability to find such numbers.)


texts: Arbitrary length to multiple of block size

texts:
I would like to apply CTR mode on a arbitrary length which isn't multiple of block size. Is this possible without applying padding.

In case we apply padding - how does the decryption algorithm know this padding!?


texts: Attack on RSA when I know $e$, ciphertexts $c_1, c_2$ of the same message $m$ with 2 coprime modules?

texts:
I know that the same message $m$ was sent to two people resulting in ciphertexts $c_1, c_2$. The public keys are $n_1$ and $n_2$, $gcd(n_1, n_2) = 1$. And $e=3$ in both cases. How can I retrieve the original message without brute-forcing it?

I.e. the exponent $e$ is the same in both public keys, but the modulus $n$ is different: $n_1, n_2$.


texts:
I am looking at the primal attack against schemes in the second round of the NIST Post-Quantum Standardization Project. The cost of primal attack usually comes from an estimate described in NewHope which says that the error vector $e$ can be found if
$$\sqrt{\beta}\sigma\leq \delta^{2\beta-d-1}\text{Vol}(\Lambda)^{1/d}\quad\quad (1)$$

My concern is with the term $\sigma$ which is the standard deviation of the distribution from which vector $e$ is sampled. If the scheme is based on Learning with Errors problem (like FrodoKEM...), then the authors always specify this value. When the scheme is based on Learning with Rounding problem then I found in the specification document of Round5 formula how to calculate the deviation error $\sigma$. However, for the NTRU-based schemes (NTRU, NTRUprime) I could not find any formula for $\sigma$ and therefore I am not able to use the (1) estimation for primal attack  (though in the specification document of NTRU and NTRUprime the cost of primal attack is evaluated).

Do you know how to estimate the cost of primal attack for the NTRU-based schemes? I.e. how to compute $\sigma$ for these schemes?


texts: What are some examples of out of bound channels that work over the Internet in practice?

texts: If I want to verify a public key (be it RSA, PGP, etc.) with another client over the Internet only, what are some viable out-of-bound channels for verification? Which channels have been used in practice and worked?


texts: What is proactive secret sharing scheme?

texts: In some papers, they just wrote that proactive secret sharing scheme is a secret sharing scheme which its shares are periodically updated. Does it have formal definition ?


texts: If curve bn256/bls12 support the isomorphism from $G_2$ to $G_1$?

texts:
Is bn256 or bls12 a type-2 pairing-friendly curve?

As Dan Boneh said here

  While in many pairing instantiations this ψ exists naturally, in some instantiations it does not.

However I can not find the isomorphism function in related library like bls12 and bn256.