Standards bodies have been addressing the key-wrap problem, a cryptographic goal that has never received a provable-security treatment. In this paper, the authors provide one, giving definitions, constructions, and proofs. They suggest that key-wrap's goal is security in the sense of Deterministic Authenticated-Encryption (DAE), a notion that they put forward. They also provide an alternative notion, a Pseudo-Random Injection (PRI), which they prove to be equivalent. They provide a DAE construction, SIV, analyze its concrete security, develop a block cipher-based instantiation of it, and suggest that the method makes a desirable alternative to the schemes of the X9.102 draft standard.