math/big: add Int.FillBytes #35833

FiloSottile · 2019-11-25T22:28:20Z

When implementing cryptography, what we need is almost always a fixed size buffer representing a value in big endian. What math/big.Int.Bytes provides is a variable size buffer, so all over the place there are snippets of code that do make, Bytes and copy with a len dependent index. I just implemented one the other day for https://golang.org/cl/208484, and just saw one in x/crypto/acme.

I'd be willing to bet that every Bytes invocation in a crypto package is doing something similar. I also learned that random bugs that occur approximately every 256 executions are probably due to missing this step, and I have found such a bug in the wild at least twice.

I propose we solve this at the math/big API level, and add (*math/big.Int).BytesWithSize.

// BytesWithSize returns the absolute value of x as a big-endian
// byte slice of length size. If x doesn't fit in such a buffer,
// BytesWithSize will panic.
func (x *Int) BytesWithSize(size int) []byte {
	b := x.Bytes()
	switch {
	case len(b) > size:
		panic("math/big: value won't fit requested size")
	case len(b) == size:
		return b
	default:
		buf := make([]byte, size)
		copy(buf[size-len(b):], b)
		return buf
	}
}

I don't have a strong opinion on the len(b) > size behavior. Where we use it in crypto packages we always know an upper bound, and if we cross it we might as well panic because something went catastrophically wrong. (And the current code would either panic or silently truncate, which is worse.)

/cc @griesemer @katiehockman

The text was updated successfully, but these errors were encountered:

griesemer · 2019-11-25T22:58:10Z

Would it make sense to provide the byte slice to avoid a copy?

func (x *Int) AsBytes(buf []byte)

robpike · 2019-11-26T06:44:09Z

Yes, I like @griesemer's design. Panic is OK if documented. A nil argument could allocate, perhaps?
That is, if you provide a buffer it must be big enough; otherwise one will be allocated.

FiloSottile · 2019-11-26T06:51:32Z

Oh, I like that!

The nil argument behavior would make sense if we didn't have Bytes, but that's there to stay.

I am not a fan of the fact that one can't really tell which is which based on the names (Bytes vs. AsBytes) but I don't have better suggestions. Maybe BytesWithBuffer? It's a mouthful but hopefully clear? WriteBytes?

magical · 2019-11-26T16:55:44Z

ToFixedBytes? Since the difference from Bytes is that it writes to a fixed-size array (with left padding).

WriteBytes?

The usual name for this would be Read, not Write 😉

griesemer · 2019-11-26T17:53:30Z

My original thought was also Read, but that name suggests that there's a result (n int, err error) as well which is perhaps overkill, especially if we never expect an error and if we don't care about the n since the buffer will be 0-padded. Also, given a Read method, one would expect a client to be able to call Read repeatedly to get all the bytes of an Int, which is not the case.

Maybe FillBytes if you don't like AsBytes? The former implies more of an "action" (of filling in the bytes) rather than a function call (that returns a value) as does the latter.

FiloSottile · 2019-12-02T20:48:34Z

I like FillBytes, thank you!

// FillBytes sets buf to the absolute value of x in big-endian, zero
// padded as necessary. If x doesn't fit in buf, FillBytes will panic.
func (x *Int) FillBytes(buf []byte)

robpike · 2019-12-02T23:35:29Z

// FillBytes sets buf to the absolute value of x, storing it as a zero-extended
// big-endian byte stream. If the encoded value doesn't fit in buf, FillBytes will panic.
func (x *Int) FillBytes(buf []byte)

robpike · 2019-12-02T23:36:53Z

I'm a little unsettled by the absolute value thing, but that's what Bytes does.

FiloSottile · 2019-12-03T05:59:41Z

I'm a little unsettled by the absolute value thing, but that's what Bytes does.

Same, but on the other hand every way of encoding negative numbers I know of went terribly wrong, so I see where that choice is coming from.

rsc · 2019-12-11T18:59:18Z

Based on the discussion, this sounds like a likely accept.

Leaving open for a week for final comments.

rsc · 2020-01-08T18:05:39Z

No final comments, so accepted.

gopherbot · 2020-04-28T02:10:10Z

Change https://golang.org/cl/230397 mentions this issue: math/big: add (*Int).FillBytes

FiloSottile · 2020-04-28T02:11:56Z

Implemented this in CL 230397.

Note that I made FillBytes return the buffer, because it was nicer to use in all call sites I updated. Let me know if there are objections to that.

Replaced almost every use of Bytes with FillBytes. Note that the approved proposal was for func (*Int) FillBytes(buf []byte) while this implements func (*Int) FillBytes(buf []byte) []byte because the latter was far nicer to use in all callsites. Fixes golang#35833 Change-Id: Ia912df123e5d79b763845312ea3d9a8051343c0a Reviewed-on: https://go-review.googlesource.com/c/go/+/230397 Reviewed-by: Robert Griesemer <gri@golang.org>

FiloSottile · 2020-05-08T00:10:31Z

Fixed by c9d5f60, which for some reason didn't close this.

Replaced almost every use of Bytes with FillBytes. Note that the approved proposal was for func (*Int) FillBytes(buf []byte) while this implements func (*Int) FillBytes(buf []byte) []byte because the latter was far nicer to use in all callsites. Fixes golang#35833 Change-Id: Ia912df123e5d79b763845312ea3d9a8051343c0a Reviewed-on: https://go-review.googlesource.com/c/go/+/230397 Reviewed-by: Robert Griesemer <gri@golang.org>

lukechampine · 2020-09-28T17:38:04Z

Sorry for not commenting earlier, but can I ask why an append-style API wasn't used here? If all I saw was the signature:

func (*Int) FillBytes(buf []byte) []byte

I would assume that it behaved like (hash.Hash).Sum (and friends), i.e. that FillBytes(nil) was equivalent to Bytes(). Given that it returns a slice, I certainly wouldn't expect it to panic.

I don't think we can change the behavior now, unfortunately, but maybe an AppendBytes is warranted...?

FiloSottile · 2020-09-28T22:54:22Z

@lukechampine What this API was specifically addressing, more than the performance advantage of saving an allocation, was the need to fill a fixed-size buffer with a possibly shorter big.Int, because big.Ints don't have an innate size. There is no way to do that with an append-like API.

lukechampine · 2020-09-29T04:30:32Z

Ah, because of the big-endianness, right. Thanks for the clarification.

gopherbot added this to the Proposal milestone Nov 25, 2019

gopherbot added the Proposal label Nov 25, 2019

rsc added this to Incoming in Proposals (old) Dec 4, 2019

rsc changed the title ~~proposal: math/big: add Int.BytesWithSize~~ proposal: math/big: add Int.FillBytes Dec 11, 2019

rsc moved this from Incoming to Likely Accept in Proposals (old) Dec 11, 2019

rsc added the Proposal-FinalCommentPeriod label Dec 11, 2019

rsc mentioned this issue Dec 11, 2019

proposal: review meeting minutes #33502

Open

rsc moved this from Likely Accept to Accepted in Proposals (old) Jan 8, 2020

rsc changed the title ~~proposal: math/big: add Int.FillBytes~~ math/big: add Int.FillBytes Jan 8, 2020

rsc modified the milestones: Proposal, Backlog Jan 8, 2020

rsc added Proposal-Accepted and removed Proposal-FinalCommentPeriod labels Jan 8, 2020

FiloSottile modified the milestones: Backlog, Go1.15 Jan 8, 2020

FiloSottile assigned FiloSottile and katiehockman Jan 8, 2020

FiloSottile added the NeedsFix The path to resolution is known, but the work has not been done. label Feb 7, 2020

FiloSottile unassigned katiehockman Mar 20, 2020

FiloSottile closed this as completed May 8, 2020

ianlancetaylor mentioned this issue Jun 12, 2020

api: audit for Go 1.15 go1.15.txt #39489

Closed

cuonglm mentioned this issue Jun 8, 2021

hybrid/subtle: use big.Int.FillBytes when ComputeSharedSecret tink-crypto/tink#516

Merged

xc added a commit to digimakergo/digimaker that referenced this issue Aug 2, 2021

updated: jwt version (need go v1.5. ref: golang/go#35833)

ced7c94

golang locked and limited conversation to collaborators Sep 29, 2021

gopherbot added the FrozenDueToAge label Sep 29, 2021

rsc unassigned FiloSottile Jun 23, 2022

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

math/big: add Int.FillBytes #35833

math/big: add Int.FillBytes #35833

FiloSottile commented Nov 25, 2019

griesemer commented Nov 25, 2019

robpike commented Nov 26, 2019

FiloSottile commented Nov 26, 2019

magical commented Nov 26, 2019

griesemer commented Nov 26, 2019

FiloSottile commented Dec 2, 2019

robpike commented Dec 2, 2019

robpike commented Dec 2, 2019

FiloSottile commented Dec 3, 2019

rsc commented Dec 11, 2019 •

edited

rsc commented Jan 8, 2020

gopherbot commented Apr 28, 2020

FiloSottile commented Apr 28, 2020

FiloSottile commented May 8, 2020

lukechampine commented Sep 28, 2020

FiloSottile commented Sep 28, 2020

lukechampine commented Sep 29, 2020

math/big: add Int.FillBytes #35833

math/big: add Int.FillBytes #35833

Comments

FiloSottile commented Nov 25, 2019

griesemer commented Nov 25, 2019

robpike commented Nov 26, 2019

FiloSottile commented Nov 26, 2019

magical commented Nov 26, 2019

griesemer commented Nov 26, 2019

FiloSottile commented Dec 2, 2019

robpike commented Dec 2, 2019

robpike commented Dec 2, 2019

FiloSottile commented Dec 3, 2019

rsc commented Dec 11, 2019 • edited

rsc commented Jan 8, 2020

gopherbot commented Apr 28, 2020

FiloSottile commented Apr 28, 2020

FiloSottile commented May 8, 2020

lukechampine commented Sep 28, 2020

FiloSottile commented Sep 28, 2020

lukechampine commented Sep 29, 2020

rsc commented Dec 11, 2019 •

edited