Constant time big numbers for Go

Related tags

Utilities safenum
Overview

safenum

The purpose of this package is to provide a version of arbitrary sized arithmetic, in a safe (i.e. constant-time) way, for cryptography.

This is experimental software, use at your own peril.

Assembly

This code reuses some assembly routines from Go's standard library, inside of the arith*.go. These have been adjusted to remove some non-constant-time codepaths, most of which aren't used anyways.

Integrating with Go

Initially, this code was structured to be relatively straightforwardly patched into Go's standard library. The idea would be to use the arith*.go files already in Go's math/big package, and just add a num.go file.

Unfortunately, this approach doesn't seem to be possible, because of addVWlarge and subVWlarge, which are two non-constant time routines. These are jumped to inside of the assembly code in Go's math/big routines, so using them would require intrusive modification, which rules out this code living alongside math/big, and sharing its routines.

Merging things upstream

The easiest path towards merging this work upstream, in all likelihood, is having this package live in crypto, and duplicating some of the assembly code as necessary.

The rationale here is that math/big's needs will inevitably lead to situations like this, where a routine is tempted to bail towards a non-constant time variant for large or special inputs. Ultimately, having this code live in crypto is much more likely to allow us to ensure its integrity. It would also allow us to add assembly specifically tailored for our operations, such as conditional addition, and things like that.

Benchmarks

Run with assembly routines:

go test -bench=.

Run with pure Go code:

go test -bench=. -tags math_big_pure_go

Licensing

The files arith*.go come from Go's standard library, and are licensed under a BSD license in LICENSE_go. The rest of the code is under an MIT license.

Comments
  • riscv64 support

    riscv64 support

    Hello @cronokirby!

    I wanted to run the ProtonMail proton-bridge software on my riscv64 machine.

    As riscv64 is in its early days, this lead me to building proton-bridge from source which for most things golang actually works fine since ca 2020 when it got supported.

    But, then this library comes by and when building gives me the below errors.

    Now, looking at the repo and its file names, I assume a file arith_riscv64.s is needed (?) - I own riscv64 hardware (a HiFive Unmatched) and am happy to dig into this. How can I contribute? What would be the best path forward here?

    ➜  proton-bridge git:(master) make build-nogui                
    go build -tags='' -ldflags '-X github.com/ProtonMail/proton-bridge/internal/constants.Version=2.1.2+git -X github.com/ProtonMail/proton-bridge/internal/constants.Revision=3b07121f08 -X github.com/ProtonMail/proton-bridge/internal/constants.BuildTime=2022-04-10T11:17:16+0000' -o proton-bridge cmd/Desktop-Bridge/main.go
    # github.com/cronokirby/saferith
    vendor/github.com/cronokirby/saferith/arith_decl.go:10:6: missing function body
    vendor/github.com/cronokirby/saferith/arith_decl.go:11:6: missing function body
    vendor/github.com/cronokirby/saferith/arith_decl.go:12:6: missing function body
    vendor/github.com/cronokirby/saferith/arith_decl.go:13:6: missing function body
    vendor/github.com/cronokirby/saferith/arith_decl.go:14:6: missing function body
    vendor/github.com/cronokirby/saferith/arith_decl.go:15:6: missing function body
    vendor/github.com/cronokirby/saferith/arith_decl.go:16:6: missing function body
    make: *** [Makefile:69: build-nogui] Error 2
    ➜  proton-bridge git:(master) 
    
    opened by olof-nord 5
  • Add assembly implementations for arm, arm64 and x86

    Add assembly implementations for arm, arm64 and x86

    To use safenum in protonmail's mobile applications, we'd like to add arm, arm64 and x86 support. I've copied the assembly implementations from big.Int and removed the non-needed implementations, similar to what was done for amd64. However I'm not sure if the code is constant time, I've seen that for amd64 some calls for 'large' subroutines were removed, I haven't found similar calls in the other archs.

    opened by marinthiercelin 1
  • Unable to target WASM

    Unable to target WASM

    When attempting to target wasm for compilation there are missing implementations

    GOOS=js GOARCH=wasm go build -tags main.wasm -o init.go
    # github.com/cronokirby/safenum
    ./arith_decl.go:10:6: missing function body
    ./arith_decl.go:11:6: missing function body
    ./arith_decl.go:12:6: missing function body
    ./arith_decl.go:13:6: missing function body
    ./arith_decl.go:14:6: missing function body
    ./arith_decl.go:15:6: missing function body
    ./arith_decl.go:16:6: missing function body
    
    opened by joshLong145 0
  • Add support for all assembly architectures

    Add support for all assembly architectures

    This copies the assembly files from https://cs.opensource.google/go/go/+/master:src/math/big/, to add support for all of the architectures supported by math/big. Most of these just jump to the pure implementations, and shouldn't pose any constant-timeness issues.

    The only one I'm somewhat unsure about is the s390x implementation, which does some loop unrolling for small limbed numbers, but it doesn't do early returns based on the evaluation results, like the amd64 did, before we modified it.

    This should address #48, but I haven't tested building and running the tests, so closing that issue is pending on doing that.

    opened by cronokirby 0
  • Fix issues for devices with 32 bit architectures

    Fix issues for devices with 32 bit architectures

    Fix issues where the implementation incorrectly assumed that the device was using words of 64 bits, leading to crashes and incorrect results on devices with 32 bit archs

    opened by marinthiercelin 0
  • `Coprime` panics on 0 length `Nat`

    `Coprime` panics on 0 length `Nat`

    When a, b = new(Nat), new(Nat), a.Coprime(b) panics since it accesses the first limb. Since both a and b are the same, the expected result would be 0.

    opened by adr1anh 0
  • Fix `Nat.Rsh` and make test more robust.

    Fix `Nat.Rsh` and make test more robust.

    • Setting x := new(Nat).Rsh(y, s, -1) would result in x not being updated.
    • Added a test that would catch this, and tests the inverse round-trip with Lsh.
    • Use the random generator to determine the size of the numbers generated for the quick tests. We ensure they are less than 128 bytes.
    • Fixed some edge cases in tests that assumed that the len(x.limbs) > 0.
    opened by adr1anh 0
  • Implement encoding.Binary{Marshaler, Unmarshaler}

    Implement encoding.Binary{Marshaler, Unmarshaler}

    These functions are simple wrappers around Nat.SetBytes() and Nat.Bytes().

    For Modulus, we additionally call precomputeValues() in UnmarshalBinary().

    Int returns byte(i.sign) || i.nat.Bytes(), so that the result is always at least one byte long. Only the LSB of of the first byte is actually used.

    Also includes test to check that MarshalBinary() -> UnmarshalBinary() returns the same result.

    opened by adr1anh 0
  • Add IsUnit method

    Add IsUnit method

    Or something like that. Right now, you can use CoPrime between two nats, but what we really want somewhat often is to check if a Nat x is a coprime to a modulus n. This would be better phrased as checking if x is a unit mod n.

    enhancement 
    opened by cronokirby 0
  • Make announced size a precise number of bits

    Make announced size a precise number of bits

    Fixes #14.

    This will be very useful for unbounded calculations, since it avoids bit explosion. This also adds support for omitting the bound passed to an operation, using a smart default instead.

    opened by cronokirby 0
  • Define signed integer abstraction

    Define signed integer abstraction

    We can't and don't need to support negative values in all places, but a few operations are actually needed, and can be implemented relatively easily, in a constant-time way:

    • Multiplication
    • Addition
    • Converting to Nat via modular reduction
    • Converting from Nat via modular reduction and range
    • Checking in modular range
    enhancement 
    opened by cronokirby 0
  • Add fuzzing code for Nat, Modulus, and Int

    Add fuzzing code for Nat, Modulus, and Int

    This adds the fuzzing code that resulted in d39f5a274f7c3b8c8d60456b1525cce26ffacfe7. These fuzz functions are written for dvyukov/go-fuzz.

    All-in-all it's quite extensive and perhaps it fuzzes some stuff that may seem to trivial to fuzz. I'd be happy to remove parts of it if that's preferred and I also welcome any suggestions for how to improve the tests.

    I put it together such that you can run these commands:

    # get go-fuzz
    $ go get -u github.com/dvyukov/go-fuzz/[email protected] github.com/dvyukov/go-fuzz/[email protected]
    
    # build fuzz binary
    $ go-fuzz-build
    
    # run fuzzer on Nat
    $ go-fuzz -workdir ./_fuzz_nat -func FuzzNat
    
    # or run fuzzer on Int
    $ go-fuzz -workdir ./_fuzz_int -func FuzzInt
    

    to fuzz everything. Or run something more specific, e.g.:

    # run fuzzer on Nat.ModSqrt
    $ go-fuzz -workdir ./_fuzz_nat -func FuzzNatSqrt
    

    to fuzz a specific (set of) function(s). The former is easier to use (just one run to fuzz everything) while the latter can be more efficient (because coverage guiding can do its job better and non-zero return values can be used).

    opened by ericcornelissen 0
Owner
Lúcás Meier
undefined is not a function
Lúcás Meier
Encriptator using random generated numbers

public-private-key-encrypter Encriptator using random generated numbers The input file must be in one file called 'data.txt' The execution will genera

Juan Diego Mejía 1 Oct 15, 2021
A golang library to validate and format swiss social security numbers

s3n is a golang library to validate and format swiss social security numbers (aka. AVS in french and AHV in german).

Julien M'Poy 0 Nov 15, 2021
Utilities for rounding and truncating floating point numbers.

Rounders Provides utilities for rounding and truncating floating point numbers. Example: rounders.RoundToDecimals(12.48881, 2)

Konnor Klashinsky 0 Jan 6, 2022
GoApiRandom - Api to get random numbers

GoApiRandom - Api to get random numbers

bdobrosielski 0 Jan 18, 2022
Meteoric golang nitro sniper, 0.1/0.5s claim time.

Meteoric golang nitro sniper, 0.1/0.5s claim time.

Azael 298 Apr 3, 2021
A simple API for computing diffs of your documents over the time built on a scalable technology stack.

Diffme API WIP - this is an API to compute diffs between documents. It serves as a way to easily create audit logs for documents in your system, think

diffme 11 Sep 8, 2021
Clean-Swift source and test code auto-generator. It can save you time typing 500-600 lines of code.

Clean-Swift source & test code auto generator Overview Run Output Basic Usage make config.yaml target_project_name: Miro // target project name copyri

David Ha 20 Apr 13, 2022
Continuous profiling for analysis of CPU, memory usage over time, and down to the line number. Saving infrastructure cost, improving performance, and increasing reliability.

Continuous profiling for analysis of CPU, memory usage over time, and down to the line number. Saving infrastructure cost, improving performance, and increasing reliability.

Parca 2.8k Jan 2, 2023
Daypaper sets your GNOME wallpaper based on the time of day from a random and relevant Unsplash image.

Daypaper Daypaper sets your GNOME wallpaper based on the time of day from a random and relevant Unsplash image. Installation You will need an Access T

Matteo Guglielmetti 15 May 23, 2022
Cell is a Go package that creates new instances by string in running time.

Cell Cell is a Go package that creates new instances by string in running time. Getting Started Installing To start using CELL, install Go and run go

null 0 Dec 20, 2021
Go Parrot Twap will execute buy or sell orders over a specific time interval.

Go Parrot Twap Go Parrot Twap will execute buy or sell orders over a specific time interval. Getting started Firstly copy the .env.example to .env and

null 17 Dec 13, 2022
A Go library for calculating the sunset/sunrise time from a given location.

solar A library for calculating the sunset/sunrise time from a given location, as well as a function to calculate the whitepoint. It is a port of ~ken

null 7 Nov 28, 2021
Cpu-profiling - Basic example of CPU Profiling in Golang which shows the bottlenecks and how much time is spent per function

cpu-profiling Basic example of CPU Profiling in Golang which shows the bottlenec

Felipe Azevedo 0 Aug 2, 2022
Argon2 password hashing package for go with constant time hash comparison

argon2pw Argon2 password hashing package with constant time hash comparison Preface: Argon2 was selected as the winner of the Password Hashing Competi

Raja Bhatia 89 Sep 27, 2022
Pure Go implementation of D. J. Bernstein's cdb constant database library.

Pure Go implementation of D. J. Bernstein's cdb constant database library.

John Barham 224 Oct 19, 2022
Find in Go repeated strings that could be replaced by a constant

goconst Find repeated strings that could be replaced by a constant. Motivation There are obvious benefits to using constants instead of repeating stri

Jonathan Gautheron 231 Jan 3, 2023
Constant Database native golang implementation

CDB golang implementation cdb is a fast, reliable, simple package for creating and reading constant databases see docs for more details Advantages Ite

Alexander Petrov 32 Jul 15, 2022
Active Directory & Red-Team Cheat-Sheet in constant expansion.

This AD attacks CheatSheet, made by RistBS is inspired by the Active-Directory-Exploitation-Cheat-Sheet repo. Edit : Thanks for 100 stars :D it is the

null 768 Jan 4, 2023
Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time.

vEB Go implementation of the van Emde Boas tree data structure: Priority queue for positive whole numbers in O(log log u) time. Supports the following

null 4 Mar 7, 2022
Fast thread-safe inmemory cache for big number of entries in Go. Minimizes GC overhead

fastcache - fast thread-safe inmemory cache for big number of entries in Go Features Fast. Performance scales on multi-core CPUs. See benchmark result

VictoriaMetrics 1.6k Dec 30, 2022