Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Add sha3 #1

Open
wants to merge 406 commits into
base: main
Choose a base branch
from
Open

Add sha3 #1

wants to merge 406 commits into from

Conversation

fdupress
Copy link

@fdupress fdupress commented Dec 6, 2023

This merges in the core proof and config files for the SHA3 security proof.

The proof currently fails with default config (but it should pass with Alt-Ergo 2.4.2) and the config file retains some jasmin-related gunk.

I can amend the folder structure while preserving history if desired, which we should discuss.

@fdupress fdupress self-assigned this Dec 6, 2023
@fdupress fdupress requested a review from strub December 6, 2023 23:45
@strub strub linked an issue Dec 7, 2023 that may be closed by this pull request
@strub
Copy link
Contributor

strub commented Dec 7, 2023

We need #2 first. This should be a no-brainer

@fdupress
Copy link
Author

fdupress commented Dec 7, 2023

We need #2 first. This should be a no-brainer

Absolutely. I just wanted to get started on extracting and collection proofs, and couldn't make the PR draft for some reason.

@strub
Copy link
Contributor

strub commented Dec 7, 2023

So, the main question is whether we want to keep the history. If so, all the sha3 commits should be rerooted under the sha3 directory. Currently, I cannot even rebase that PR on top of main.

@fdupress
Copy link
Author

fdupress commented Dec 7, 2023

The SHA3 history can't rebase cleanly on an empty repo for some reason. This current version is a subtree into sha3, followed by a filter-repo to remove all implementation-related history.

A final commit adds sha3 to the repo's CI and updates the test config (including prover selection for now).

fdupress and others added 22 commits December 8, 2023 21:28
…me reason."

This reverts commit 7e32f742fa318b19e41ab7d99d39496645304427.
the  folder may have contained useful stuff. Check history if needed.
There's an unrestricted smt left in RP.ec, because of the goal:

d_ll: is_lossless dt
d_fu: support dt = predT
&m: memory <P.f>
h : exists (x : t), ! mem (rng P.m{m}) x
------------------------------------------------------------------------
mu dt (mem (rng P.m{m})) < 1%r

After a quick look, I'm not seeing what combination of distribution
lemmas says that if the support of a distribution d is all of a type t
and some element of t doesn't satisfy a predicate P, that mu d P
< 1.
Maybe the following lemma would be useful addition to EC Library,
as it works well with dexcepted_ll?

lemma mu_except ['a] (d : 'a distr, y : 'a, P : 'a -> bool) :
  is_lossless d => support d = predT => ! P y => mu d P < 1%r.

(Francois just used this logic in IdealPRP.ec; as he says,
maybe we should be using that instead of RP.ec.)
lemma mu_except ['a] (d : 'a distr, y : 'a, P : 'a -> bool) :
  in_supp y d => ! P y => mu d P < mu d predT.

And simplified use of it.
syntax.

I haven't updated the files in the "core" subdirectory, several of
which are now failing to parse.
New and improved functor system really helped with debugging.
@fdupress
Copy link
Author

fdupress commented Dec 8, 2023

History now replayed (and fiddled with in that one merge commit that git insisted on resolving using a different strategy) on top of main. Please do not merge #5 first :)

@fdupress
Copy link
Author

fdupress commented Dec 9, 2023

Alright, @strub. This now checks SHA3 (with Alt-Ergo 2.4).

I'm still not 100% sure I like the whole history being dropped in and (later) mingled into other proofs' histories, but if this is going to be the repo of reference for these proofs, then the history is good to keep.

Perhaps a good halfway point would be to have one repo per proof with history, but with the folder structure we'd like to ultimately have in here (so the subtree is easy), and integrate proofs here as squashed subtrees via GitHub actions?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Import SHA3 security proof
4 participants