a geicko-2 based round robin ranking system designed to test c++ battleship submissions
battleship.dunkirk.sh
dunkirk.sh
1// Copyright 2012 The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE file.
4
5package ssh
6
7import (
8 "bytes"
9 "errors"
10 "fmt"
11 "io"
12 "net"
13 "sort"
14 "time"
15)
16
17// Certificate algorithm names from [PROTOCOL.certkeys]. These values can appear
18// in Certificate.Type, PublicKey.Type, and ClientConfig.HostKeyAlgorithms.
19// Unlike key algorithm names, these are not passed to AlgorithmSigner nor
20// returned by MultiAlgorithmSigner and don't appear in the Signature.Format
21// field.
22const (
23 CertAlgoRSAv01 = "ssh-rsa-cert-v01@openssh.com"
24 // Deprecated: DSA is only supported at insecure key sizes, and was removed
25 // from major implementations.
26 CertAlgoDSAv01 = InsecureCertAlgoDSAv01
27 // Deprecated: DSA is only supported at insecure key sizes, and was removed
28 // from major implementations.
29 InsecureCertAlgoDSAv01 = "ssh-dss-cert-v01@openssh.com"
30 CertAlgoECDSA256v01 = "ecdsa-sha2-nistp256-cert-v01@openssh.com"
31 CertAlgoECDSA384v01 = "ecdsa-sha2-nistp384-cert-v01@openssh.com"
32 CertAlgoECDSA521v01 = "ecdsa-sha2-nistp521-cert-v01@openssh.com"
33 CertAlgoSKECDSA256v01 = "sk-ecdsa-sha2-nistp256-cert-v01@openssh.com"
34 CertAlgoED25519v01 = "ssh-ed25519-cert-v01@openssh.com"
35 CertAlgoSKED25519v01 = "sk-ssh-ed25519-cert-v01@openssh.com"
36
37 // CertAlgoRSASHA256v01 and CertAlgoRSASHA512v01 can't appear as a
38 // Certificate.Type (or PublicKey.Type), but only in
39 // ClientConfig.HostKeyAlgorithms.
40 CertAlgoRSASHA256v01 = "rsa-sha2-256-cert-v01@openssh.com"
41 CertAlgoRSASHA512v01 = "rsa-sha2-512-cert-v01@openssh.com"
42)
43
44const (
45 // Deprecated: use CertAlgoRSAv01.
46 CertSigAlgoRSAv01 = CertAlgoRSAv01
47 // Deprecated: use CertAlgoRSASHA256v01.
48 CertSigAlgoRSASHA2256v01 = CertAlgoRSASHA256v01
49 // Deprecated: use CertAlgoRSASHA512v01.
50 CertSigAlgoRSASHA2512v01 = CertAlgoRSASHA512v01
51)
52
53// Certificate types distinguish between host and user
54// certificates. The values can be set in the CertType field of
55// Certificate.
56const (
57 UserCert = 1
58 HostCert = 2
59)
60
61// Signature represents a cryptographic signature.
62type Signature struct {
63 Format string
64 Blob []byte
65 Rest []byte `ssh:"rest"`
66}
67
68// CertTimeInfinity can be used for OpenSSHCertV01.ValidBefore to indicate that
69// a certificate does not expire.
70const CertTimeInfinity = 1<<64 - 1
71
72// An Certificate represents an OpenSSH certificate as defined in
73// [PROTOCOL.certkeys]?rev=1.8. The Certificate type implements the
74// PublicKey interface, so it can be unmarshaled using
75// ParsePublicKey.
76type Certificate struct {
77 Nonce []byte
78 Key PublicKey
79 Serial uint64
80 CertType uint32
81 KeyId string
82 ValidPrincipals []string
83 ValidAfter uint64
84 ValidBefore uint64
85 Permissions
86 Reserved []byte
87 SignatureKey PublicKey
88 Signature *Signature
89}
90
91// genericCertData holds the key-independent part of the certificate data.
92// Overall, certificates contain an nonce, public key fields and
93// key-independent fields.
94type genericCertData struct {
95 Serial uint64
96 CertType uint32
97 KeyId string
98 ValidPrincipals []byte
99 ValidAfter uint64
100 ValidBefore uint64
101 CriticalOptions []byte
102 Extensions []byte
103 Reserved []byte
104 SignatureKey []byte
105 Signature []byte
106}
107
108func marshalStringList(namelist []string) []byte {
109 var to []byte
110 for _, name := range namelist {
111 s := struct{ N string }{name}
112 to = append(to, Marshal(&s)...)
113 }
114 return to
115}
116
117type optionsTuple struct {
118 Key string
119 Value []byte
120}
121
122type optionsTupleValue struct {
123 Value string
124}
125
126// serialize a map of critical options or extensions
127// issue #10569 - per [PROTOCOL.certkeys] and SSH implementation,
128// we need two length prefixes for a non-empty string value
129func marshalTuples(tups map[string]string) []byte {
130 keys := make([]string, 0, len(tups))
131 for key := range tups {
132 keys = append(keys, key)
133 }
134 sort.Strings(keys)
135
136 var ret []byte
137 for _, key := range keys {
138 s := optionsTuple{Key: key}
139 if value := tups[key]; len(value) > 0 {
140 s.Value = Marshal(&optionsTupleValue{value})
141 }
142 ret = append(ret, Marshal(&s)...)
143 }
144 return ret
145}
146
147// issue #10569 - per [PROTOCOL.certkeys] and SSH implementation,
148// we need two length prefixes for a non-empty option value
149func parseTuples(in []byte) (map[string]string, error) {
150 tups := map[string]string{}
151 var lastKey string
152 var haveLastKey bool
153
154 for len(in) > 0 {
155 var key, val, extra []byte
156 var ok bool
157
158 if key, in, ok = parseString(in); !ok {
159 return nil, errShortRead
160 }
161 keyStr := string(key)
162 // according to [PROTOCOL.certkeys], the names must be in
163 // lexical order.
164 if haveLastKey && keyStr <= lastKey {
165 return nil, fmt.Errorf("ssh: certificate options are not in lexical order")
166 }
167 lastKey, haveLastKey = keyStr, true
168 // the next field is a data field, which if non-empty has a string embedded
169 if val, in, ok = parseString(in); !ok {
170 return nil, errShortRead
171 }
172 if len(val) > 0 {
173 val, extra, ok = parseString(val)
174 if !ok {
175 return nil, errShortRead
176 }
177 if len(extra) > 0 {
178 return nil, fmt.Errorf("ssh: unexpected trailing data after certificate option value")
179 }
180 tups[keyStr] = string(val)
181 } else {
182 tups[keyStr] = ""
183 }
184 }
185 return tups, nil
186}
187
188func parseCert(in []byte, privAlgo string) (*Certificate, error) {
189 nonce, rest, ok := parseString(in)
190 if !ok {
191 return nil, errShortRead
192 }
193
194 key, rest, err := parsePubKey(rest, privAlgo)
195 if err != nil {
196 return nil, err
197 }
198
199 var g genericCertData
200 if err := Unmarshal(rest, &g); err != nil {
201 return nil, err
202 }
203
204 c := &Certificate{
205 Nonce: nonce,
206 Key: key,
207 Serial: g.Serial,
208 CertType: g.CertType,
209 KeyId: g.KeyId,
210 ValidAfter: g.ValidAfter,
211 ValidBefore: g.ValidBefore,
212 }
213
214 for principals := g.ValidPrincipals; len(principals) > 0; {
215 principal, rest, ok := parseString(principals)
216 if !ok {
217 return nil, errShortRead
218 }
219 c.ValidPrincipals = append(c.ValidPrincipals, string(principal))
220 principals = rest
221 }
222
223 c.CriticalOptions, err = parseTuples(g.CriticalOptions)
224 if err != nil {
225 return nil, err
226 }
227 c.Extensions, err = parseTuples(g.Extensions)
228 if err != nil {
229 return nil, err
230 }
231 c.Reserved = g.Reserved
232 k, err := ParsePublicKey(g.SignatureKey)
233 if err != nil {
234 return nil, err
235 }
236 // The Type() function is intended to return only certificate key types, but
237 // we use certKeyAlgoNames anyway for safety, to match [Certificate.Type].
238 if _, ok := certKeyAlgoNames[k.Type()]; ok {
239 return nil, fmt.Errorf("ssh: the signature key type %q is invalid for certificates", k.Type())
240 }
241 c.SignatureKey = k
242 c.Signature, rest, ok = parseSignatureBody(g.Signature)
243 if !ok || len(rest) > 0 {
244 return nil, errors.New("ssh: signature parse error")
245 }
246
247 return c, nil
248}
249
250type openSSHCertSigner struct {
251 pub *Certificate
252 signer Signer
253}
254
255type algorithmOpenSSHCertSigner struct {
256 *openSSHCertSigner
257 algorithmSigner AlgorithmSigner
258}
259
260// NewCertSigner returns a Signer that signs with the given Certificate, whose
261// private key is held by signer. It returns an error if the public key in cert
262// doesn't match the key used by signer.
263func NewCertSigner(cert *Certificate, signer Signer) (Signer, error) {
264 if !bytes.Equal(cert.Key.Marshal(), signer.PublicKey().Marshal()) {
265 return nil, errors.New("ssh: signer and cert have different public key")
266 }
267
268 switch s := signer.(type) {
269 case MultiAlgorithmSigner:
270 return &multiAlgorithmSigner{
271 AlgorithmSigner: &algorithmOpenSSHCertSigner{
272 &openSSHCertSigner{cert, signer}, s},
273 supportedAlgorithms: s.Algorithms(),
274 }, nil
275 case AlgorithmSigner:
276 return &algorithmOpenSSHCertSigner{
277 &openSSHCertSigner{cert, signer}, s}, nil
278 default:
279 return &openSSHCertSigner{cert, signer}, nil
280 }
281}
282
283func (s *openSSHCertSigner) Sign(rand io.Reader, data []byte) (*Signature, error) {
284 return s.signer.Sign(rand, data)
285}
286
287func (s *openSSHCertSigner) PublicKey() PublicKey {
288 return s.pub
289}
290
291func (s *algorithmOpenSSHCertSigner) SignWithAlgorithm(rand io.Reader, data []byte, algorithm string) (*Signature, error) {
292 return s.algorithmSigner.SignWithAlgorithm(rand, data, algorithm)
293}
294
295const sourceAddressCriticalOption = "source-address"
296
297// CertChecker does the work of verifying a certificate. Its methods
298// can be plugged into ClientConfig.HostKeyCallback and
299// ServerConfig.PublicKeyCallback. For the CertChecker to work,
300// minimally, the IsAuthority callback should be set.
301type CertChecker struct {
302 // SupportedCriticalOptions lists the CriticalOptions that the
303 // server application layer understands. These are only used
304 // for user certificates.
305 SupportedCriticalOptions []string
306
307 // IsUserAuthority should return true if the key is recognized as an
308 // authority for user certificate. This must be set if this CertChecker
309 // will be checking user certificates.
310 IsUserAuthority func(auth PublicKey) bool
311
312 // IsHostAuthority should report whether the key is recognized as
313 // an authority for this host. This must be set if this CertChecker
314 // will be checking host certificates.
315 IsHostAuthority func(auth PublicKey, address string) bool
316
317 // Clock is used for verifying time stamps. If nil, time.Now
318 // is used.
319 Clock func() time.Time
320
321 // UserKeyFallback is called when CertChecker.Authenticate encounters a
322 // public key that is not a certificate. It must implement validation
323 // of user keys or else, if nil, all such keys are rejected.
324 UserKeyFallback func(conn ConnMetadata, key PublicKey) (*Permissions, error)
325
326 // HostKeyFallback is called when CertChecker.CheckHostKey encounters a
327 // public key that is not a certificate. It must implement host key
328 // validation or else, if nil, all such keys are rejected.
329 HostKeyFallback HostKeyCallback
330
331 // IsRevoked is called for each certificate so that revocation checking
332 // can be implemented. It should return true if the given certificate
333 // is revoked and false otherwise. If nil, no certificates are
334 // considered to have been revoked.
335 IsRevoked func(cert *Certificate) bool
336}
337
338// CheckHostKey checks a host key certificate. This method can be
339// plugged into ClientConfig.HostKeyCallback.
340func (c *CertChecker) CheckHostKey(addr string, remote net.Addr, key PublicKey) error {
341 cert, ok := key.(*Certificate)
342 if !ok {
343 if c.HostKeyFallback != nil {
344 return c.HostKeyFallback(addr, remote, key)
345 }
346 return errors.New("ssh: non-certificate host key")
347 }
348 if cert.CertType != HostCert {
349 return fmt.Errorf("ssh: certificate presented as a host key has type %d", cert.CertType)
350 }
351 if !c.IsHostAuthority(cert.SignatureKey, addr) {
352 return fmt.Errorf("ssh: no authorities for hostname: %v", addr)
353 }
354
355 hostname, _, err := net.SplitHostPort(addr)
356 if err != nil {
357 return err
358 }
359
360 // Pass hostname only as principal for host certificates (consistent with OpenSSH)
361 return c.CheckCert(hostname, cert)
362}
363
364// Authenticate checks a user certificate. Authenticate can be used as
365// a value for ServerConfig.PublicKeyCallback.
366func (c *CertChecker) Authenticate(conn ConnMetadata, pubKey PublicKey) (*Permissions, error) {
367 cert, ok := pubKey.(*Certificate)
368 if !ok {
369 if c.UserKeyFallback != nil {
370 return c.UserKeyFallback(conn, pubKey)
371 }
372 return nil, errors.New("ssh: normal key pairs not accepted")
373 }
374
375 if cert.CertType != UserCert {
376 return nil, fmt.Errorf("ssh: cert has type %d", cert.CertType)
377 }
378 if !c.IsUserAuthority(cert.SignatureKey) {
379 return nil, fmt.Errorf("ssh: certificate signed by unrecognized authority")
380 }
381
382 if err := c.CheckCert(conn.User(), cert); err != nil {
383 return nil, err
384 }
385
386 return &cert.Permissions, nil
387}
388
389// CheckCert checks CriticalOptions, ValidPrincipals, revocation, timestamp and
390// the signature of the certificate.
391func (c *CertChecker) CheckCert(principal string, cert *Certificate) error {
392 if c.IsRevoked != nil && c.IsRevoked(cert) {
393 return fmt.Errorf("ssh: certificate serial %d revoked", cert.Serial)
394 }
395
396 for opt := range cert.CriticalOptions {
397 // sourceAddressCriticalOption will be enforced by
398 // serverAuthenticate
399 if opt == sourceAddressCriticalOption {
400 continue
401 }
402
403 found := false
404 for _, supp := range c.SupportedCriticalOptions {
405 if supp == opt {
406 found = true
407 break
408 }
409 }
410 if !found {
411 return fmt.Errorf("ssh: unsupported critical option %q in certificate", opt)
412 }
413 }
414
415 if len(cert.ValidPrincipals) > 0 {
416 // By default, certs are valid for all users/hosts.
417 found := false
418 for _, p := range cert.ValidPrincipals {
419 if p == principal {
420 found = true
421 break
422 }
423 }
424 if !found {
425 return fmt.Errorf("ssh: principal %q not in the set of valid principals for given certificate: %q", principal, cert.ValidPrincipals)
426 }
427 }
428
429 clock := c.Clock
430 if clock == nil {
431 clock = time.Now
432 }
433
434 unixNow := clock().Unix()
435 if after := int64(cert.ValidAfter); after < 0 || unixNow < int64(cert.ValidAfter) {
436 return fmt.Errorf("ssh: cert is not yet valid")
437 }
438 if before := int64(cert.ValidBefore); cert.ValidBefore != uint64(CertTimeInfinity) && (unixNow >= before || before < 0) {
439 return fmt.Errorf("ssh: cert has expired")
440 }
441 if err := cert.SignatureKey.Verify(cert.bytesForSigning(), cert.Signature); err != nil {
442 return fmt.Errorf("ssh: certificate signature does not verify")
443 }
444
445 return nil
446}
447
448// SignCert signs the certificate with an authority, setting the Nonce,
449// SignatureKey, and Signature fields. If the authority implements the
450// MultiAlgorithmSigner interface the first algorithm in the list is used. This
451// is useful if you want to sign with a specific algorithm. As specified in
452// [SSH-CERTS], Section 2.1.1, authority can't be a [Certificate].
453func (c *Certificate) SignCert(rand io.Reader, authority Signer) error {
454 c.Nonce = make([]byte, 32)
455 if _, err := io.ReadFull(rand, c.Nonce); err != nil {
456 return err
457 }
458 // The Type() function is intended to return only certificate key types, but
459 // we use certKeyAlgoNames anyway for safety, to match [Certificate.Type].
460 if _, ok := certKeyAlgoNames[authority.PublicKey().Type()]; ok {
461 return fmt.Errorf("ssh: certificates cannot be used as authority (public key type %q)",
462 authority.PublicKey().Type())
463 }
464 c.SignatureKey = authority.PublicKey()
465
466 if v, ok := authority.(MultiAlgorithmSigner); ok {
467 if len(v.Algorithms()) == 0 {
468 return errors.New("the provided authority has no signature algorithm")
469 }
470 // Use the first algorithm in the list.
471 sig, err := v.SignWithAlgorithm(rand, c.bytesForSigning(), v.Algorithms()[0])
472 if err != nil {
473 return err
474 }
475 c.Signature = sig
476 return nil
477 } else if v, ok := authority.(AlgorithmSigner); ok && v.PublicKey().Type() == KeyAlgoRSA {
478 // Default to KeyAlgoRSASHA512 for ssh-rsa signers.
479 // TODO: consider using KeyAlgoRSASHA256 as default.
480 sig, err := v.SignWithAlgorithm(rand, c.bytesForSigning(), KeyAlgoRSASHA512)
481 if err != nil {
482 return err
483 }
484 c.Signature = sig
485 return nil
486 }
487
488 sig, err := authority.Sign(rand, c.bytesForSigning())
489 if err != nil {
490 return err
491 }
492 c.Signature = sig
493 return nil
494}
495
496// certKeyAlgoNames is a mapping from known certificate algorithm names to the
497// corresponding public key signature algorithm.
498//
499// This map must be kept in sync with the one in agent/client.go.
500var certKeyAlgoNames = map[string]string{
501 CertAlgoRSAv01: KeyAlgoRSA,
502 CertAlgoRSASHA256v01: KeyAlgoRSASHA256,
503 CertAlgoRSASHA512v01: KeyAlgoRSASHA512,
504 InsecureCertAlgoDSAv01: InsecureKeyAlgoDSA,
505 CertAlgoECDSA256v01: KeyAlgoECDSA256,
506 CertAlgoECDSA384v01: KeyAlgoECDSA384,
507 CertAlgoECDSA521v01: KeyAlgoECDSA521,
508 CertAlgoSKECDSA256v01: KeyAlgoSKECDSA256,
509 CertAlgoED25519v01: KeyAlgoED25519,
510 CertAlgoSKED25519v01: KeyAlgoSKED25519,
511}
512
513// underlyingAlgo returns the signature algorithm associated with algo (which is
514// an advertised or negotiated public key or host key algorithm). These are
515// usually the same, except for certificate algorithms.
516func underlyingAlgo(algo string) string {
517 if a, ok := certKeyAlgoNames[algo]; ok {
518 return a
519 }
520 return algo
521}
522
523// certificateAlgo returns the certificate algorithms that uses the provided
524// underlying signature algorithm.
525func certificateAlgo(algo string) (certAlgo string, ok bool) {
526 for certName, algoName := range certKeyAlgoNames {
527 if algoName == algo {
528 return certName, true
529 }
530 }
531 return "", false
532}
533
534func (cert *Certificate) bytesForSigning() []byte {
535 c2 := *cert
536 c2.Signature = nil
537 out := c2.Marshal()
538 // Drop trailing signature length.
539 return out[:len(out)-4]
540}
541
542// Marshal serializes c into OpenSSH's wire format. It is part of the
543// PublicKey interface.
544func (c *Certificate) Marshal() []byte {
545 generic := genericCertData{
546 Serial: c.Serial,
547 CertType: c.CertType,
548 KeyId: c.KeyId,
549 ValidPrincipals: marshalStringList(c.ValidPrincipals),
550 ValidAfter: uint64(c.ValidAfter),
551 ValidBefore: uint64(c.ValidBefore),
552 CriticalOptions: marshalTuples(c.CriticalOptions),
553 Extensions: marshalTuples(c.Extensions),
554 Reserved: c.Reserved,
555 SignatureKey: c.SignatureKey.Marshal(),
556 }
557 if c.Signature != nil {
558 generic.Signature = Marshal(c.Signature)
559 }
560 genericBytes := Marshal(&generic)
561 keyBytes := c.Key.Marshal()
562 _, keyBytes, _ = parseString(keyBytes)
563 prefix := Marshal(&struct {
564 Name string
565 Nonce []byte
566 Key []byte `ssh:"rest"`
567 }{c.Type(), c.Nonce, keyBytes})
568
569 result := make([]byte, 0, len(prefix)+len(genericBytes))
570 result = append(result, prefix...)
571 result = append(result, genericBytes...)
572 return result
573}
574
575// Type returns the certificate algorithm name. It is part of the PublicKey interface.
576func (c *Certificate) Type() string {
577 certName, ok := certificateAlgo(c.Key.Type())
578 if !ok {
579 panic("unknown certificate type for key type " + c.Key.Type())
580 }
581 return certName
582}
583
584// Verify verifies a signature against the certificate's public
585// key. It is part of the PublicKey interface.
586func (c *Certificate) Verify(data []byte, sig *Signature) error {
587 return c.Key.Verify(data, sig)
588}
589
590func parseSignatureBody(in []byte) (out *Signature, rest []byte, ok bool) {
591 format, in, ok := parseString(in)
592 if !ok {
593 return
594 }
595
596 out = &Signature{
597 Format: string(format),
598 }
599
600 if out.Blob, in, ok = parseString(in); !ok {
601 return
602 }
603
604 switch out.Format {
605 case KeyAlgoSKECDSA256, CertAlgoSKECDSA256v01, KeyAlgoSKED25519, CertAlgoSKED25519v01:
606 out.Rest = in
607 return out, nil, ok
608 }
609
610 return out, in, ok
611}
612
613func parseSignature(in []byte) (out *Signature, rest []byte, ok bool) {
614 sigBytes, rest, ok := parseString(in)
615 if !ok {
616 return
617 }
618
619 out, trailing, ok := parseSignatureBody(sigBytes)
620 if !ok || len(trailing) > 0 {
621 return nil, nil, false
622 }
623 return
624}