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

Next iteration of Digest traits #20

Closed
newpavlov opened this issue Apr 10, 2017 · 10 comments
Closed

Next iteration of Digest traits #20

newpavlov opened this issue Apr 10, 2017 · 10 comments
Assignees

Comments

@newpavlov
Copy link
Member

Sacundim in his feedback on the reddit proposed to use instead of VariableOutput the following traits:

  • ExtendableOutput for functions like SHAKE from SHA-3, which allow to "read" indefinitely from the result
  • VariableOutput for functions like Groestl, which have some limits on the output size and may require output size to be known at state initalization

Also @burdges proposed to move out BlockSize from the Input trait to a separate one.

@newpavlov
Copy link
Member Author

@burdges
Probably you are right and it's worth to decouple the Input trait and BlockSize. But I think we still better to include "recommended" block sizes:

  • 512 bits for BLAKE2b and 256 bits for BLAKE2s
  • 1600 - 2*output_size bits for SHA-3 (so it will not be defined for SHAKE functions)

@burdges
Copy link

burdges commented Apr 13, 2017

I have not read the Grøstl paper but the abstract says "Grøstl is a so-called wide-pipe construction where the size of the internal state is significantly larger than the size of the output."

Do you want run-time variable output so that Grøstl could be used instead of Keccek's SHAKE mode? If so, you'll want dynamic allocation for that, and your VariableOutput mode looks exactly like ExtendableOutput except that it errors/panics if you exceed the allowed length, right?

Rust does not support dynamic stack allocation currently, but support for DSTs should improve via alloca, unsized rvalues, or dependent types. Right now, there is only minimal discussion about supporting DSTs that contain multiple DSTs inside though. If the language designers do not go for super-fat pointers then we might wind up with arena based schemes roughly like :

pub struct Groestl<Arena>
  where Arena: ?Sized+Borrow<[u64]>+BorrowMut<[u64]>
{
    arena: Arena,
}

struct GroestlRefs<'a> {
    output_size: usize,
    state: &'a mut [u64],
    buffer: &'a mut [u8],
}

impl<Arena> Groestl<Arena>
  where Self: 'a, 
        Arena: ?Sized+Borrow<[u64]>+BorrowMut<[u64]>
{
    fn refs<'a>(&'a mut self) -> GroestlRefs<'a> {
        let arena = self.arena.borrow_mut();
        let output_size = 8*arena.len()/9;
        let (state,buffer) = arena.splt_at_mut(output_size);
        let buffer = unsafe { mem::from_raw_parts_mut(buffer as *mut u64 as *mut u8, output_size) };
        GroestlRefs { output_size, state, buffer }
    }
}

so Groestl<[u64]> gives a DST while Groestl<[u64; 8*O/9]> gives the fixed size type with output_size = O. Assuming fixed length arrays get impl Trait for [T, b] of course.

@newpavlov
Copy link
Member Author

Groestl can't operate as XOF, because size of the output influences IV, thus output length must be known at digest initialization. (see section 3.5 of the paper)

As I stated in the reddit discussion I am thinking about writing VariableOutput trait like this:

trait VariableOutput<'a>: Sized {
    fn new(buf: &'a mut [u8]) -> Result<Self, InvalidLength>;
    
    fn variable_result(self) -> &'a [u8];
}

Here length of the buf will determine output length of variable_result result, as it will be essentially the same buffer.

It's not ideal as requirement to pass buffer could be unnecessary restrictive for some hashes. (e.g. BLAKE2 defines "variable" output as a simple truncation) But I think it will be better compared to creation of yet another trait.

Regarding alloca there is concerns about performance issues of using dynamically sized structs on the stack, so I think it will be better to stick with the buffer approach.

@burdges
Copy link

burdges commented Apr 30, 2017

Rust language team expects "const generics available on nightly by the end of 2017".

In my opinion, library interfaces that expose generic array crate should therefore be slated for deprecation in 2018, after const generics reach stability. I'd hoped they might stabilize FixedSizzeArray soonish so that library interfaces could build on that instead of generic array, but no luck.

For now, I'd suggest creating a trait that covers the desired fixed length array types, but which you can deprecate without fear of breaking anything :

/// Fixed size array of bytes of lengths that commonly appear as outputs of cryptographic functions.
///
/// This trait is an unstable hack until Rust gets type level numerics.  It will be deprecated in future
/// so do not use it if you want stability. 
pub trait FixedSizeByteArray {
    fn length_in_bytes() -> { core::mem::size_of::<Self>() } 
    fn length_in_bits() -> { 8 * Self::length_in_bytes() }
    fn as_slice(&self) -> &[u8];
    fn as_mut_slice(&mut self) -> &mut [u8];
}
macro_rules! impl_FixedSizeByteArray {
    impl FixedSizeByteArray for [u8; $l] {
        fn as_slice(&self) -> &[u8] {self }
        fn as_mut_slice(&mut self) -> &mut [u8] {self }
    }
}
impl_FixedSizeByteArray!(16);
impl_FixedSizeByteArray!(32);
impl_FixedSizeByteArray!(64);
impl_FixedSizeByteArray!(128);
impl_FixedSizeByteArray!(256);

The benefit is that code that does not need to be polymorphic on array length can use these hash functions without breaking in future.

@newpavlov
Copy link
Member Author

@burdges
Not sure how it will work and if it's worth to work on it until we at least get const generics on nightly. Also I think it's better to just bump a new minor version of crates without any transitions.

@burdges
Copy link

burdges commented May 5, 2017

I mentioned this here mostly because if you were going to redesign digest in a big way soon anyways, then you could maybe future proof it, but no reason to rush anything. :)

@burdges
Copy link

burdges commented May 12, 2017

The new const generics RFC looks worth watching : rust-lang/rfcs#2000

@newpavlov
Copy link
Member Author

@burdges
Thank you for the link!

@newpavlov
Copy link
Member Author

I've updated crates to digest v0.6. Feel free to create new issues if you'll have suggestions about API.

@burdges
Copy link

burdges commented Jun 14, 2017

I'm thrilled to see VariableOutput make an appearance. Just fyi, there is an emerging consensus to use the SHAKE-128/256 or cSHAKE modes, not the fixed output SHA-3 modes, as the competition's requirements mistakenly conflated the security level ad output size. If you design a new protocol using Keccek/SHA-3 then you should probably avoid the modes that do FixedOutput as they seem needlessly slow in software.

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

No branches or pull requests

2 participants