2 * Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
4 * Permission is hereby granted, free of charge, to any person obtaining
5 * a copy of this software and associated documentation files (the
6 * "Software"), to deal in the Software without restriction, including
7 * without limitation the rights to use, copy, modify, merge, publish,
8 * distribute, sublicense, and/or sell copies of the Software, and to
9 * permit persons to whom the Software is furnished to do so, subject to
10 * the following conditions:
12 * The above copyright notice and this permission notice shall be
13 * included in all copies or substantial portions of the Software.
15 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
16 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
17 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
18 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
19 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
20 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
21 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
26 using System.Collections.Generic;
35 * Class for a SSL server connection.
37 * An instance is created over a specified transport stream. An optional
38 * cache for session parameters can be provided, to support session
39 * resumption. The instance handles the connection but cannot be
40 * "revived" after the connection was closed (the session parameters,
41 * though, can be extracted and used with another instance).
44 public class SSLServer : SSLEngine {
47 * If true, then the server will enforce its own preference
48 * order for cipher suite selection; otherwise, it will follow
49 * the client's preferences. Default value is false.
51 public bool EnforceServerOrder {
56 * Server policy object, that selects cipher suite and certificate
57 * chain to send to client. Such a policy object MUST be set
58 * before the initial handshake takes place. This property is
59 * initialised to the value provided as second argument to the
60 * SSLServer constructor.
62 public IServerPolicy ServerPolicy {
67 * Optional session cache for SSL sessions. If null, then no
68 * cache is used. Default value is null.
70 public ISessionCache SessionCache {
75 * If this flag is set to true, then session resumption will be
76 * rejected; all handshakes will be full handshakes. Main
77 * intended usage is when a server wants to renegotiate and ask
78 * for a client certificate. Note that even if that flag is set,
79 * each session resulting from a full handshake is still pushed
80 * to the session cache (if configured in SessionCache).
81 * Default value is false, meaning that session resumption is
82 * allowed (but won't happen anyway if no session cache was
83 * set in SessionCache).
85 public bool NoResume {
90 * Get the maximum supported version announced by the client
91 * in its ClientHello message.
93 public int ClientVersionMax {
98 * Get the list of hash and signature algorithms supported by the
99 * client. Each value is a 16-bit integer, with the high byte
100 * being the hash algorithm, and the low byte the signature
103 * The list is trimmed to include only hash and signature algorithms
104 * that are supported by both client and server. It is ordered
105 * by client or server preference, depending on the value of
106 * the EnforceServerOrder flag.
108 * If the client did not send the dedicated extension, then the
109 * list is inferred from the sent cipher suite, as specified
110 * by RFC 5246, section 7.4.1.4.1.
112 public List<int> ClientHashAndSign {
117 * Get the list of elliptic curves supported by the client. Each
118 * entry is a 16-bit integer that identifies a named curve. The
119 * list is ordered by client preferences.
121 * If the client did not send the Supported Curves extension,
122 * then the list will be inferred to contain NIST P-256 only
123 * (if the client supports at least one ECDH, ECDHE or ECDSA
124 * cipher suite), or to be empty (if the client does not support
125 * any EC-based cipher suite).
127 public List<int> ClientCurves {
132 * Get the list of elliptic curves supported by both client and
133 * server. Each entry is a 16-bit integer that identifies a
134 * named curve. The list is ordered by preference (client or
135 * server, depending on configuration). This list is the one
136 * used for curve selection for ECDHE.
138 public List<int> CommonCurves {
143 * Get the list of cipher suites supported by the client. The
144 * order matches the configured preferences (client or server
145 * preference order, depending on the EnforceServerOrder flag).
146 * Moreover, the list is trimmed:
148 * - Signalling cipher suites ("SCSV") have been removed.
150 * - Only suites supported by both client and server are kept.
152 * - Suites that require TLS 1.2 are omitted if the selected
153 * protocol version is TLS 1.0 or 1.1.
155 * - Suites that require client support for RSA signatures are
156 * removed if there is no common support for RSA signatures.
158 * - Suites that require client support for ECDSA signatures
159 * are removed if there is no common support for ECDSA
162 * - ECDHE suites are removed if there is no common support for
165 public List<int> CommonCipherSuites {
169 IServerChoices serverChoices;
174 * Create an SSL server instance, over the provided stream.
175 * The 'serverPolicy' parameter is used as initial value to
176 * the ServerPolicy property.
178 public SSLServer(Stream sub, IServerPolicy serverPolicy)
181 EnforceServerOrder = false;
182 ServerPolicy = serverPolicy;
185 internal override bool IsClient {
191 internal override bool DoHandshake()
193 CheckConfigHashAndSign();
196 MakeRandom(serverRandom);
199 if (!ParseClientHello(out resume)) {
203 SetOutputRecordVersion(Version);
204 SetInputRecordVersion(Version);
208 SendCCSAndFinished();
210 ParseCCSAndFinished();
218 if (SSL.IsECDHE(CipherSuite)) {
219 SendServerKeyExchange();
221 SendServerHelloDone();
224 ParseClientKeyExchange();
225 ParseCCSAndFinished();
226 SendCCSAndFinished();
230 if (SessionCache != null) {
231 SessionCache.Store(SessionParameters);
236 bool ParseClientHello(out bool resume)
240 byte[] msg = ReadHandshakeMessage(out mt, FirstHandshakeDone);
243 * Client rejected renegotiation attempt. This cannot
244 * happen if we are invoked from
245 * ProcessExtraHandshake() because that method is
246 * invoked only when there is buffered handshake
251 if (mt != SSL.CLIENT_HELLO) {
252 throw new SSLException(string.Format("Unexpected"
253 + " handshake message {0} (expecting a"
254 + " ClientHello)", mt));
258 * Maximum protocol version supported by the client.
260 if (msg.Length < 35) {
261 throw new SSLException("Invalid ClientHello");
263 ClientVersionMax = IO.Dec16be(msg, 0);
264 if (ClientVersionMax < VersionMin) {
265 throw new SSLException(string.Format(
266 "No acceptable version (client max = 0x{0:X4})",
271 * Client random (32 bytes).
273 Array.Copy(msg, 2, clientRandom, 0, 32);
276 * Session ID sent by the client: at most 32 bytes.
280 if (idLen > 32 || (off + idLen) > msg.Length) {
281 throw new SSLException("Invalid ClientHello");
283 byte[] clientSessionID = new byte[idLen];
284 Array.Copy(msg, off, clientSessionID, 0, idLen);
288 * List of client cipher suites.
290 if ((off + 2) > msg.Length) {
291 throw new SSLException("Invalid ClientHello");
293 int csLen = IO.Dec16be(msg, off);
295 if ((off + csLen) > msg.Length) {
296 throw new SSLException("Invalid ClientHello");
298 List<int> clientSuites = new List<int>();
299 bool seenReneg = false;
301 int cs = IO.Dec16be(msg, off);
304 if (cs == SSL.FALLBACK_SCSV) {
305 if (ClientVersionMax < VersionMax) {
306 throw new SSLException(
307 "Undue fallback detected");
309 } else if (cs == SSL.EMPTY_RENEGOTIATION_INFO_SCSV) {
310 if (FirstHandshakeDone) {
311 throw new SSLException(
312 "Reneg SCSV in renegotiation");
316 clientSuites.Add(cs);
321 * List of compression methods. We only accept method 0
324 if ((off + 1) > msg.Length) {
325 throw new SSLException("Invalid ClientHello");
327 int compLen = msg[off ++];
328 if ((off + compLen) > msg.Length) {
329 throw new SSLException("Invalid ClientHello");
331 bool foundUncompressed = false;
332 while (compLen -- > 0) {
333 if (msg[off ++] == 0x00) {
334 foundUncompressed = true;
337 if (!foundUncompressed) {
338 throw new SSLException("No common compression support");
344 ClientHashAndSign = null;
346 if (off < msg.Length) {
347 if ((off + 2) > msg.Length) {
348 throw new SSLException("Invalid ClientHello");
350 int tlen = IO.Dec16be(msg, off);
352 if ((off + tlen) != msg.Length) {
353 throw new SSLException("Invalid ClientHello");
355 while (off < msg.Length) {
356 if ((off + 4) > msg.Length) {
357 throw new SSLException(
358 "Invalid ClientHello");
360 int etype = IO.Dec16be(msg, off);
361 int elen = IO.Dec16be(msg, off + 2);
363 if ((off + elen) > msg.Length) {
364 throw new SSLException(
365 "Invalid ClientHello");
370 ParseExtSNI(msg, off, elen);
374 ParseExtSignatures(msg, off, elen);
378 ParseExtCurves(msg, off, elen);
382 ParseExtSecureReneg(msg, off, elen);
396 * If we are renegotiating and we did not see the
397 * Secure Renegotiation extension, then this is an error.
399 if (FirstHandshakeDone && !seenReneg) {
400 throw new SSLException(
401 "Missing Secure Renegotiation extension");
405 * Use prescribed default values for supported algorithms
406 * and curves, when not otherwise advertised by the client.
408 if (ClientCurves == null) {
409 ClientCurves = new List<int>();
410 foreach (int cs in clientSuites) {
411 if (SSL.IsECDH(cs) || SSL.IsECDHE(cs)) {
412 ClientCurves.Add(SSL.NIST_P256);
417 if (ClientHashAndSign == null) {
418 bool withRSA = false;
419 bool withECDSA = false;
420 foreach (int cs in clientSuites) {
422 || SSL.IsECDH_RSA(cs)
423 || SSL.IsECDHE_RSA(cs))
427 if (SSL.IsECDH_ECDSA(cs)
428 || SSL.IsECDHE_ECDSA(cs))
433 ClientHashAndSign = new List<int>();
435 ClientHashAndSign.Add(SSL.RSA_SHA1);
438 ClientHashAndSign.Add(SSL.ECDSA_SHA1);
443 * Filter curves and algorithms with regards to our own
446 CommonCurves = FilterList(ClientCurves,
447 SupportedCurves, EnforceServerOrder);
448 ClientHashAndSign = FilterList(ClientHashAndSign,
449 SupportedHashAndSign, EnforceServerOrder);
452 * Selected protocol version (can be overridden by
455 Version = Math.Min(ClientVersionMax, VersionMax);
456 string forcedVersion = GetQuirkString("forceVersion");
457 if (forcedVersion != null) {
458 switch (forcedVersion) {
459 case "TLS10": Version = SSL.TLS10; break;
460 case "TLS11": Version = SSL.TLS11; break;
461 case "TLS12": Version = SSL.TLS12; break;
463 throw new Exception(string.Format(
464 "Unknown forced version: '{0}'",
470 * Recompute list of acceptable cipher suites. We keep
471 * only suites which are common to the client and server,
472 * with some extra filters.
474 * Note that when using static ECDH, it is up to the
475 * policy callback to determine whether the curves match
476 * the contents of the certificate.
478 * We also build a list of common suites for session
479 * resumption: this one may include suites whose
480 * asymmetric crypto is not supported, because session
481 * resumption uses only symmetric crypto.
483 CommonCipherSuites = new List<int>();
484 List<int> commonSuitesResume = new List<int>();
485 bool canTLS12 = Version >= SSL.TLS12;
486 bool mustTLS12 = false;
487 if (GetQuirkBool("forceTls12CipherSuite")) {
493 if (Version >= SSL.TLS12) {
495 canSignECDSA = false;
496 foreach (int alg in ClientHashAndSign) {
499 case SSL.RSA: canSignRSA = true; break;
500 case SSL.ECDSA: canSignECDSA = true; break;
505 * For pre-1.2, the hash-and-sign configuration does
506 * not matter, only the cipher suites themselves. So
507 * we claim support of both RSA and ECDSA signatures
508 * to avoid trimming the list too much.
513 bool canECDHE = CommonCurves.Count > 0;
515 foreach (int cs in clientSuites) {
516 if (!canTLS12 && SSL.IsTLS12(cs)) {
519 if (mustTLS12 && !SSL.IsTLS12(cs)) {
522 commonSuitesResume.Add(cs);
523 if (!canECDHE && SSL.IsECDHE(cs)) {
526 if (!canSignRSA && SSL.IsECDHE_RSA(cs)) {
529 if (!canSignECDSA && SSL.IsECDHE_ECDSA(cs)) {
532 CommonCipherSuites.Add(cs);
534 CommonCipherSuites = FilterList(CommonCipherSuites,
535 SupportedCipherSuites, EnforceServerOrder);
536 commonSuitesResume = FilterList(commonSuitesResume,
537 SupportedCipherSuites, EnforceServerOrder);
540 * If resuming, then use the remembered session parameters,
541 * but only if they are compatible with what the client
542 * sent AND what we currently support.
544 SSLSessionParameters sp = null;
545 if (idLen > 0 && !NoResume && SessionCache != null) {
546 sp = SessionCache.Retrieve(
547 clientSessionID, ServerName);
548 if (sp != null && sp.ServerName != null
549 && ServerName != null)
552 * When resuming a session, if there is
553 * an explicit name sent by the client,
554 * and the cached parameters also include
555 * an explicit name, then both names
558 string s1 = sp.ServerName.ToLowerInvariant();
559 string s2 = ServerName.ToLowerInvariant();
566 bool resumeOK = true;
567 if (sp.Version < VersionMin
568 || sp.Version > VersionMax
569 || sp.Version > ClientVersionMax)
573 if (!commonSuitesResume.Contains(sp.CipherSuite)) {
579 * Session resumption is acceptable.
582 sessionID = clientSessionID;
583 Version = sp.Version;
584 CipherSuite = sp.CipherSuite;
585 sessionID = clientSessionID;
586 SetMasterSecret(sp.MasterSecret);
592 * Not resuming. Let's select parameters.
593 * Protocol version was already set.
595 if (CommonCipherSuites.Count == 0) {
596 throw new SSLException("No common cipher suite");
598 serverChoices = ServerPolicy.Apply(this);
599 CipherSuite = serverChoices.GetCipherSuite();
602 * We create a new session ID, even if we don't have a
603 * session cache, because the session parameters could
604 * be extracted manually by the application.
606 sessionID = new byte[32];
607 RNG.GetBytes(sessionID);
612 void ParseExtSNI(byte[] buf, int off, int len)
615 throw new SSLException("Invalid SNI extension");
617 int tlen = IO.Dec16be(buf, off);
619 if ((tlen + 2) != len) {
620 throw new SSLException("Invalid SNI extension");
622 int lim = off + tlen;
625 if ((off + 3) > lim) {
626 throw new SSLException("Invalid SNI extension");
628 int ntype = buf[off ++];
629 int nlen = IO.Dec16be(buf, off);
631 if ((off + nlen) > lim) {
632 throw new SSLException("Invalid SNI extension");
636 * Name type is "host name". There shall be
637 * only one (at most) in the extension.
640 throw new SSLException("Several host"
641 + " names in SNI extension");
646 * Verify that the name contains only
647 * printable non-space ASCII, and normalise
650 char[] tc = new char[nlen];
651 for (int i = 0; i < nlen; i ++) {
652 int x = buf[off + i];
653 if (x <= 32 || x >= 126) {
654 throw new SSLException(
655 "Invalid SNI hostname");
657 if (x >= 'A' && x <= 'Z') {
662 ServerName = new string(tc);
668 void ParseExtSignatures(byte[] buf, int off, int len)
671 throw new SSLException("Invalid signatures extension");
673 int tlen = IO.Dec16be(buf, off);
675 if (len != (tlen + 2)) {
676 throw new SSLException("Invalid signatures extension");
678 if ((tlen & 1) != 0) {
679 throw new SSLException("Invalid signatures extension");
681 ClientHashAndSign = new List<int>();
683 ClientHashAndSign.Add(IO.Dec16be(buf, off));
689 void ParseExtCurves(byte[] buf, int off, int len)
692 throw new SSLException("Invalid curves extension");
694 int tlen = IO.Dec16be(buf, off);
696 if (len != (tlen + 2)) {
697 throw new SSLException("Invalid curves extension");
699 if ((tlen & 1) != 0) {
700 throw new SSLException("Invalid curves extension");
702 ClientCurves = new List<int>();
704 ClientCurves.Add(IO.Dec16be(buf, off));
710 void ParseExtSecureReneg(byte[] buf, int off, int len)
712 if (len < 1 || len != 1 + buf[off]) {
713 throw new SSLException(
714 "Invalid Secure Renegotiation extension");
719 if (renegSupport == 0) {
721 * Initial handshake: extension MUST be empty.
724 throw new SSLException(
725 "Non-empty Secure Renegotation"
726 + " on initial handshake");
731 * Renegotiation: extension MUST contain the
732 * saved client Finished message.
735 throw new SSLException(
736 "Wrong Secure Renegotiation value");
739 for (int i = 0; i < 12; i ++) {
740 z |= savedClientFinished[i] ^ buf[off + i];
743 throw new SSLException(
744 "Wrong Secure Renegotiation value");
749 void SendServerHello()
751 MemoryStream ms = StartHandshakeMessage(SSL.SERVER_HELLO);
754 IO.Write16(ms, Version);
757 ms.Write(serverRandom, 0, serverRandom.Length);
760 ms.WriteByte((byte)sessionID.Length);
761 ms.Write(sessionID, 0, sessionID.Length);
764 IO.Write16(ms, CipherSuite);
770 MemoryStream chExt = new MemoryStream();
772 // Secure renegotiation
773 if (!GetQuirkBool("noSecureReneg")) {
775 if (renegSupport > 0) {
776 if (FirstHandshakeDone) {
778 Array.Copy(savedClientFinished, 0,
780 Array.Copy(savedServerFinished, 0,
786 if (GetQuirkBool("forceEmptySecureReneg")) {
788 } else if (GetQuirkBool("forceNonEmptySecureReneg")) {
790 } else if (GetQuirkBool("alterNonEmptySecureReneg")) {
791 if (exv.Length > 0) {
792 exv[exv.Length - 1] ^= 0x01;
794 } else if (GetQuirkBool("oversizedSecureReneg")) {
799 IO.Write16(chExt, 0xFF01);
800 IO.Write16(chExt, exv.Length + 1);
801 chExt.WriteByte((byte)exv.Length);
802 chExt.Write(exv, 0, exv.Length);
806 // Extra extension with random contents.
807 int extraExt = GetQuirkInt("sendExtraExtension", -1);
809 byte[] exv = new byte[extraExt >> 16];
811 IO.Write16(chExt, extraExt & 0xFFFF);
812 IO.Write16(chExt, exv.Length);
813 chExt.Write(exv, 0, exv.Length);
816 // Max Fragment Length
820 byte[] encExt = chExt.ToArray();
821 if (encExt.Length > 0) {
822 if (encExt.Length > 65535) {
823 throw new SSLException("Oversized extensions");
825 IO.Write16(ms, encExt.Length);
826 ms.Write(encExt, 0, encExt.Length);
829 EndHandshakeMessage(ms);
832 void SendCertificate()
834 MemoryStream ms = StartHandshakeMessage(SSL.CERTIFICATE);
835 byte[][] chain = serverChoices.GetCertificateChain();
837 foreach (byte[] ec in chain) {
838 tlen += 3 + ec.Length;
840 if (tlen > 0xFFFFFC) {
841 throw new SSLException("Oversized certificate chain");
843 IO.Write24(ms, tlen);
844 foreach (byte[] ec in chain) {
845 IO.Write24(ms, ec.Length);
846 ms.Write(ec, 0, ec.Length);
848 EndHandshakeMessage(ms);
851 void SendServerKeyExchange()
853 if (CommonCurves.Count == 0) {
855 * Since we filter cipher suites when parsing the
856 * ClientHello, this situation may happen only if
857 * the IServerPolicy callback goofed up.
859 throw new SSLException("No curve for ECDHE");
861 int curveID = CommonCurves[0];
862 ecdheCurve = SSL.GetCurveByID(curveID);
865 * Generate our ephemeral ECDH secret and the point to
868 ecdheSecret = ecdheCurve.MakeRandomSecret();
869 byte[] P = ecdheCurve.GetGenerator(false);
870 ecdheCurve.Mul(P, ecdheSecret, P, false);
873 * Generate to-be-signed:
874 * clientRandom 32 bytes
875 * serverRandom 32 bytes
876 * 0x03 curve is a "named curve"
877 * id curve identifier (two bytes)
878 * point public point (one-byte length + value)
880 byte[] tbs = new byte[64 + 4 + P.Length];
881 Array.Copy(clientRandom, 0, tbs, 0, 32);
882 Array.Copy(serverRandom, 0, tbs, 32, 32);
884 IO.Enc16be(curveID, tbs, 65);
885 tbs[67] = (byte)P.Length;
886 Array.Copy(P, 0, tbs, 68, P.Length);
889 * Obtain server signature.
891 int hashAlgo, sigAlgo;
892 byte[] sig = serverChoices.DoSign(tbs,
893 out hashAlgo, out sigAlgo);
898 MemoryStream ms = StartHandshakeMessage(
899 SSL.SERVER_KEY_EXCHANGE);
900 ms.Write(tbs, 64, tbs.Length - 64);
901 if (Version >= SSL.TLS12) {
902 ms.WriteByte((byte)hashAlgo);
903 ms.WriteByte((byte)sigAlgo);
905 IO.Write16(ms, sig.Length);
906 ms.Write(sig, 0, sig.Length);
907 EndHandshakeMessage(ms);
910 void SendServerHelloDone()
912 MemoryStream ms = StartHandshakeMessage(SSL.SERVER_HELLO_DONE);
913 EndHandshakeMessage(ms);
916 void ParseClientKeyExchange()
918 byte[] msg = ReadHandshakeMessageExpected(
919 SSL.CLIENT_KEY_EXCHANGE);
921 if (SSL.IsECDHE(CipherSuite)) {
923 * Expecting a curve point; we are doing the
926 if (msg.Length < 1 || msg.Length != 1 + msg[0]) {
927 throw new SSLException(
928 "Invalid ClientKeyExchange");
930 byte[] P = new byte[msg.Length - 1];
931 byte[] D = new byte[ecdheCurve.EncodedLength];
932 Array.Copy(msg, 1, P, 0, P.Length);
933 if (ecdheCurve.Mul(P, ecdheSecret, D, false) == 0) {
934 throw new SSLException(
935 "Invalid ClientKeyExchange");
938 int xoff = ecdheCurve.GetXoff(out xlen);
939 pms = new byte[xlen];
940 Array.Copy(D, xoff, pms, 0, xlen);
943 * Memory wiping is out of scope for this library,
944 * and is unreliable anyway in the presence of
945 * a moving garbage collector. So we just unlink
951 * RSA or static ECDH. The crypto operation is done
952 * by the relevant callback.
954 if (msg.Length < 2) {
955 throw new SSLException(
956 "Invalid ClientKeyExchange");
959 if (SSL.IsRSA(CipherSuite)) {
960 len = IO.Dec16be(msg, 0);
962 } else if (SSL.IsECDH(CipherSuite)) {
966 throw new Exception("NYI");
968 if (msg.Length != off + len) {
969 throw new SSLException(
970 "Invalid ClientKeyExchange");
972 byte[] cke = new byte[len];
973 Array.Copy(msg, off, cke, 0, len);
974 pms = serverChoices.DoKeyExchange(cke);
980 internal override void ProcessExtraHandshake()
983 * If Secure Renegotiation is supported, then we accept
984 * to do a new handshake.
986 if (renegSupport > 0) {
992 * We must read and discard an incoming ClientHello,
993 * then politely refuse.
995 ReadHandshakeMessageExpected(SSL.CLIENT_HELLO);
996 SendWarning(SSL.NO_RENEGOTIATION);
1000 internal override void PrepareRenegotiate()
1002 MemoryStream ms = StartHandshakeMessage(SSL.HELLO_REQUEST);
1003 EndHandshakeMessage(ms);
1008 * Compute the intersection of two lists of integers (the second
1009 * list is provided as an array). The intersection is returned
1010 * as a new List<int> instance. If enforceV2 is true, then the
1011 * order of items in the returned list will be that of v2; otherwise,
1012 * it will be that of v1. Duplicates are removed.
1014 static List<int> FilterList(List<int> v1, int[] v2, bool enforceV2)
1016 List<int> r = new List<int>();
1018 foreach (int x in v2) {
1019 if (v1.Contains(x) && !r.Contains(x)) {
1024 foreach (int x in v1) {
1025 foreach (int y in v2) {
1027 if (!r.Contains(x)) {